P12097 [NERC2024] Fix Flooded Floor
题目描述
阿基米德进行了他的著名浮力实验。但是少有人知道,他洗澡时太过专注,没有注意到水从浴缸边溢出,使他的木地板发生了不可逆的破坏。
阿基米德发现,并非所有地板都损坏了,还剩下一些地板是完好的。墙边的木地板区域形状为 $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$ 个字符,表示木地板的状态,其中 $\texttt{.}$ 表示损坏的区域,$\texttt{\#}$ 表示完好的区域。
总共 $T$ 个测试用例中 $\sum n$ 不超过 $2 \cdot 10^5$ 。
输出格式
对于每个测试用例,若恰好存在一种修复的方式,输出 $\tt{Unique}$;,若存在多种方式,输出 $\tt{Mutiple}$;若无法修复,输出 $\tt{None}$。