← 返回题目列表

Codeforces · 2052/F

F. 修复被淹的地板

中文机器翻译题面 查看原题

阿基米德进行了他著名的浮力实验。但并不是所有人都知道,他在洗澡的时候,太过专注,没有注意到水溢出浴缸边缘,淹没靠近墙壁的地板的那一刻。他昂贵的镶木地板受到了不可逆转的损坏!

阿基米德注意到并没有全部丢失,还有几块未损坏的镶木地板。靠近墙壁的镶木地板的形状是一条由 $$$2\times n$$$ 单元组成的狭长条纹。阿基米德无限量供应 $$$1\times 2$$$ 镶木地板,可以平行或垂直于墙壁放置。阿基米德不想切割镶木地板碎片。作为一位伟大的科学家,他发现只有一种方法可以修复镶木地板,即用不重叠的 $$$1\times 2$$$ 细胞形状的碎片填充镶木地板的受损区域。

帮助历史学家检查阿基米德的计算。对于 $$$2\times n$$$ 镶木地板的给定配置,确定是否存在一种方法可以用 $$$1\times 2$$$ 单元格镶木地板填充损坏的镶木地板单元。如果阿基米德错了,找出是否有多种方法可以恢复镶木地板,或者根本没有方法。

输入

第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 10^4$$$) — 要解决的测试用例的数量。

然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — 镶木地板的长度。

以下两行每行包含 $$$n$$$ 个字符并描述镶木地板,其中 '.' 表示损坏的细胞并且 '#'表示未损坏的单元。

所有$$$T$$$测试用例中$$$n$$$的总和不超过$$$2\cdot 10^5$$$。

输出

对于每个测试用例,打印“独特“如果只有一种方法可以恢复镶木地板,”多个“如果有多种方法可以做到这一点,或者”无“如果无法恢复镶木地板。

示例

输入
复制

4
10
#.......##
##..#.##..
6
...#..
..#...
8
........
........
3
###
###

输出
复制

Unique
None
Multiple
Unique