Omkar 正在使用彩色方形瓷砖创建马赛克,他将其放置在 $$$n \times n$$$ 网格中。当马赛克完成时,网格中的每个单元格将具有白釉或红釉瓷砖。不过,目前他只在一些牢房里放置了瓷砖。
当且仅当每个图块恰好与相同颜色的 $$$2$$$ 图块相邻时,完整的马赛克才是 Masapeece(如果共享一侧,$$$2$$$ 图块就是相邻的。)Omkar 想要填充其余的图块,以便马赛克成为 Masapeece。现在他想知道,这样做的方法是否独特?如果是,那是什么?
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2000$$$)。
然后跟随 $$$n$$$ 行,每行包含 $$$n$$$ 个字符。第 $$$j$$$ 行中的第 $$$i$$$ 字符对应于网格的 $$$i$$$ 行和 $$$j$$$ 列中的单元格,如果 Omkar 在该单元格中放置了 sinoper 瓷砖,则为 $$$S$$$;如果 Omkar 在该单元格中放置了 glaucous 瓷砖,则为 $$$G$$$;如果为空,则为 $$$.$$$。
输出
在第一行,如果有一种独特的方法来获取 Masapeece,则打印 UNIQUE;如果 Omkar 无法创建任何 Masapeece,则打印 NONE;如果有多种方法可以创建 Masapeece,则打印 MULTIPLE。所有字母必须大写。
如果打印 UNIQUE,则打印 $$$n$$$ 附加行,每行包含 $$$n$$$ 个字符,这样,如果 mastapeece 的 $$$i$$$ 行和 $$$j$$$ 列中的图块为 sinoper,则 $$$j^{\text{th}}$$$ 行中的第 $$$i$$$ 字符为 $$$S$$$,并且$$$G$$$ 如果是白霜的话。
示例
输入 #1
4 S... ..G. .... ...S
输出 #1
MULTIPLE
输入 #2
6 S..... ....G. ..S... .....S ....G. G.....
输出 #2
NONE
输入 #3
10 .S....S... .......... ...SSS.... .......... .......... ...GS..... ....G...G. .......... ......G... ..........
输出 #3
UNIQUE SSSSSSSSSS SGGGGGGGGS SGSSSSSSGS SGSGGGGSGS SGSGSSGSGS SGSGSSGSGS SGSGGGGSGS SGSSSSSSGS SGGGGGGGGS SSSSSSSSSS
输入#4
1 .
输出#4
NONE
注意
对于第一个测试用例,Omkar 可以制作 mastapeeces
SSSS
SGGS
SGGS
SSSS
和
SSGG
SSGG
GGSS
GGSS。
对于第二个测试用例,可以证明 Omkar 不可能添加图块来创建 Masapeece。
对于第三种情况,可以证明给定的 Masapeece 是 Omkar 可以通过添加图块创建的唯一 Masapeece。
对于第四个测试用例,Omkar 创建的任何马赛克中的唯一图块显然不可能与相同颜色的两个图块相邻,因为它将与总共 $$$0$$$ 图块相邻。