레이팅 미적용You are on vacation in a foreign country. This country has a local football league, and you don't know any of the team names. However, you have found a table of all the results from this season, and next to every match is the concatenated names of the two teams that played.
There are \(n\) teams in total, named \(s_1, s_2, \cdots, s_n\). You are given the concatenation \(s_i+s_j\) for every ordered pair \(i \neq j\). Find the teams names \(s_1, s_2, \cdots, s_n\). Team names must be nonempty, but they do not need to be distinct.
The first line of input contains the integer \(n\) (\(2 \leq n \leq 500\)).
The following \(n\) lines each contain \(n\) strings, the table of concatenated team names. The \(j\):th string on the \(i\):th of these lines will contain the string \(s_i + s_j\) if \(i \neq j\), and "*" if \(i = j\). The concatenated team names will consist of lower case characters a-z.
The total number of characters in concatenated team names is at most \(10^6\).
If there is no solution, print "NONE".
If there is more than one solution, print "MANY".
If there is one unique solution, print "UNIQUE", followed by \(n\) lines containing \(s_1, s_2, \cdots, s_n\).
3
* difaik difhammarby
aikdif * aikhammarby
hammarbydif hammarbyaik *
UNIQUE
dif
aik
hammarby
2
* aaaa
aaaa *
MANY
3
* a ab
a * b
ba b *
NONE
2
* zz
zz *
UNIQUE
z
z