Омкар создает мозаику, используя цветные квадратные плитки, которые он размещает в сетке \(n \times n\). Когда мозаика будет завершена, в каждой ячейке сетки будет либо глазурная, либо синоперная плитка. Однако в настоящее время он разместил плитки только в некоторых ячейках.
Завершенная мозаика будет шедевром тогда и только тогда, когда каждая плитка примыкает ровно к \(2\) плиткам того же цвета (\(2\) плитки являются примыкающими, если у них есть общая сторона.) Омкар хочет заполнить оставшиеся плитки так, чтобы мозаика стала шедевром. Теперь ему интересно, правда ли, что есть ровно один способ это сделать, и если да, то какой?
Выходные данные
В первой строке выведите UNIQUE, если существует уникальный способ получить шедевр, NONE, если Омкар не может его создать, и MULTIPLE, если существует более одного способа. Все буквы должны быть заглавными.
Если вы выведете UNIQUE, то после этого выведите \(n\) дополнительных строк с \(n\) символами в каждой строке, такими, что \(i\)-й символ в \(j^{\text{th}}\) строке будет \(S\), если плитка в строке \(i\) и столбце \(j\) шедевра — синоперная, и \(G\), если она глазурная.
Примечание
Для первого примера Омкар может получить шедевры
SSSS
SGGS
SGGS
SSSS
и
SSGG
SSGG
GGSS
GGSS.
Для второго примера можно доказать, что Омкар не может сложить плитки, чтобы создать шедевр.
Для третьего примера можно доказать, что данный шедевр — единственный шедевр, который Омкар может создать, сложив плитки.
Для четвертого примера очевидно, что единственная плитка в любой мозаике, которую создает Омкар, не может быть соседней с двумя плитками одного цвета, так как она будет соседней с \(0\) плитками.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
S...
..G.
....
...S
|
MULTIPLE
|
|
2
|
6
S.....
....G.
..S...
.....S
....G.
G.....
|
NONE
|
|
3
|
10
.S....S...
..........
...SSS....
..........
..........
...GS.....
....G...G.
..........
......G...
..........
|
UNIQUE
SSSSSSSSSS
SGGGGGGGGS
SGSSSSSSGS
SGSGGGGSGS
SGSGSSGSGS
SGSGSSGSGS
SGSGGGGSGS
SGSSSSSSGS
SGGGGGGGGS
SSSSSSSSSS
|
|
4
|
1
.
|
NONE
|