410505: GYM104030 F 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 $$$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