Foreign Football

문제

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 $nn$ teams in total, named $s_1,s_2,\cdots ,s_{n}s\_1,\; s\_2,\; \backslash cdots,\; s\_n$. You are given the concatenation $s_i+s_{j}s\_i+s\_j$ for every ordered pair $i\mathrm{\ne }ji\; \backslash neq\; j$. Find the teams names $s_1,s_2,\cdots ,s_{n}s\_1,\; s\_2,\; \backslash cdots,\; s\_n$. Team names must be nonempty, but they do not need to be distinct.

입력

The first line of input contains the integer $nn$ ($2\le n\le 5002\; \backslash leq\; n\; \backslash leq\; 500$).

The following $nn$ lines each contain $nn$ strings, the table of concatenated team names. The $jj$:th string on the $ii$:th of these lines will contain the string $s_i+s_{j}s\_i\; +\; s\_j$ if $i\mathrm{\ne }ji\; \backslash neq\; j$, and "*" if $i=ji\; =\; 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}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 $nn$ lines containing $s_1,s_2,\cdots ,s_{n}s\_1,\; s\_2,\; \backslash 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