#P13088. [AGC059E] Grid 3-coloring

[AGC059E] Grid 3-coloring

题目描述

有一个 N×NN \times N 的方格棋盘。你需要用三种颜色给所有格子染色,要求任意相邻(共享边)的两个格子颜色不同。

棋盘最外层的格子已经被染色。请判断是否可以按照要求给剩下的格子染色。

更准确地说,给定一个由字符 1、2、3 组成的长度为 4N−44N-4 的字符串 SS,该字符串表示从 (1,1)(1, 1) 开始,按顺时针顺序记录的最外层格子的颜色。具体地,第 ii 个字符表示如下格子的颜色:

  • 当 1≤i≤N−11 \leq i \leq N-1 时,对应 (1,i)(1, i);
  • 当 N≤i≤2N−2N \leq i \leq 2N-2 时,对应 (i−(N−1),N)(i - (N-1), N);
  • 当 2N−1≤i≤3N−32N-1 \leq i \leq 3N-3 时,对应 (N,3N−1−i)(N, 3N-1-i);
  • 当 3N−2≤i≤4N−43N-2 \leq i \leq 4N-4 时,对应 (4N−2−i,1)(4N-2-i, 1)。

其中,(r,c)(r, c) 表示第 rr 行第 cc 列的格子。

保证最外层格子中,任意相邻的两个格子颜色不同。

对于每个输入文件,请判断是否存在一种方案,可以用三种颜色给剩下的格子染色,使得任意相邻格子颜色不同。

输入格式

输入从标准输入读入,格式如下:

TT
case1case_1
case2case_2
⋮\vdots
caseTcase_T

每个测试用例格式如下:

NN SS

输出格式

对于每个测试用例,如果存在一种方案可以按照要求用三种颜色染色,则输出 YES,否则输出 NO。输出时不区分大小写。

输入输出样例 #1

输入 #1

4
3
12312312
4
121212121212
7
321312312312121212121321
7
321312312312121312121321

输出 #1

NO
YES
NO
YES

说明/提示

限制

  • 1≤T≤5⋅1041 \leq T \leq 5 \cdot 10^4
  • 3≤N≤2⋅1053 \leq N \leq 2 \cdot 10^5
  • SS 是由字符 1、2、3 组成的长度为 4N−44N-4 的字符串。
  • 对于 1≤i≤4N−51 \leq i \leq 4N-5,有 Si≠Si+1S_i \neq S_{i+1},且 S4N−4≠S1S_{4N-4} \neq S_1。
  • 每个输入文件中所有 NN 的总和不超过 2⋅1052 \cdot 10^5。
  • 输入中的所有数字均为整数。

样例解释 1

对于第一个和第三个测试用例,可以证明无法按照要求染色。对于第二个和第四个测试用例,下面给出了可以按照要求染色的方案。