分数: 1400 点
问题陈述
你有一个 N \times N 网格板。 您想要为所有单元格着色 3 颜色,使两个相邻(共享边缘)的单元格不具有相同的颜色。
您已经绘制了板的边框。确定是否可以正确为板的其余部分着色。
更准确地说,你得到一个字符串 S 长度 4N-4 由字符组成 1, 2,和 3。该字符串表示边框上单元格的颜色,从单元格开始 (1, 1),按顺时针顺序。
严格来说, i第一个字符 S 表示单元格的颜色:
- (1, i) 为 1 \le i \le N-1
- (i - (N-1), N) 为 N \le i \le 2N-2
- (N, 3N - 1 - i) 为 2N-1 \le i \le 3N-3
- (4N-2 - i, 1) 为 3N-2 \le i \le 4N-4.
在这里, (r,c) 表示单元格中 r第行和 c第列。
保证边界上没有两个相邻单元格具有相同的颜色。
解决 T 每个输入文件的测试用例。 一个输入文件中的
约束
- 1 \le T \le 5 \cdot 10^4
- 3 \le N \le 2 \cdot 10^5
- S 是一个长度为的字符串 4N-4 由字符组成
1,2,和3. - S_i \neq S_{i+1} 为 1 \le i \le 4N-5,和 S_{4N-4} \neq S_1.
- 总和 N 不超过 2\cdot 10^5.
- 输入中的所有数字均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例的格式如下:
N S
输出
对于每个测试用例,输出 YES 如果有办法给棋盘的其余部分着色 3 颜色正确,并且 NO 否则。您可以以任何大小写(大写或小写)输出每个字母。
示例输入 1
4 3 12312312 4 121212121212 7 321312312312121212121321 7 321312312312121312121321
示例输出 1
NO YES NO YES
可以看出,在第一个和第三个测试用例中无法正确为电路板的其余部分着色。第二个和第四个测试用例的正确颜色如下所示。
