[AGC059E] Grid 3-coloring

有一个 $n \times n$ 的网格图，网格最外面一圈的格子（即所有的 $(x,y),x\in \{1,n\} \lor y \in \{1,n\}$）已经被染色了，现在问你在已有的限制下网格图是否能 $3$ 染色。 每组数据输入两行，第一行是网格图的边长 $n$。 接下来的一行输入 $4 \times n -4 $ 个字符，依次表示从 $(1,1)$ 按顺时针顺序的所有格子的颜色。

[problemUrl]: https://atcoder.jp/contests/agc059/tasks/agc059_e $ N\ \times\ N $ のマス盤面があります。 あなたは、隣接する（辺を共有する）どの二つのマスも同じ色にならないように、すべてのマスを $ 3 $ 色で塗ろうとしています。 盤面の最も外側は、すでに塗ってしまいました。盤面の残りを意図通りに塗ることができるか判定してください。 より正確には、文字 `1`, `2`, `3` からなる長さ $ 4N-4 $ の文字列 $ S $ が与えられます。この文字列は、盤面の最も外側のマスの色を、$ (1,\ 1) $ から始めて時計回りに表します。 厳密には、$ S $ の $ i $ 文字目は次のマスの色を表します。 - $ 1\ \le\ i\ \le\ N-1 $ のとき、$ (1,\ i) $ - $ N\ \le\ i\ \le\ 2N-2 $ のとき、$ (i\ -\ (N-1),\ N) $ - $ 2N-1\ \le\ i\ \le\ 3N-3 $ のとき、$ (N,\ 3N\ -\ 1\ -\ i) $ - $ 3N-2\ \le\ i\ \le\ 4N-4 $ のとき、$ (4N-2\ -\ i,\ 1) $ ここで、$ (r,c) $ は $ r $ 行 $ c $ 列目のマスを指します。 盤面の最も外側では、隣接するどの二つのマスも同じ色でないことが保証されます。 各入力ファイルについて、$ T $ 個のテストケースを解いてください。

入力は標準入力から以下の形式で与えられる。 > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各ケースは以下の形式である。 > $ N $ $ S $

各テストケースについて、盤面の残りを意図通りに $ 3 $ 色で塗る方法があれば `YES` と、なければ `NO` と出力せよ。出力中の各文字は英大文字・小文字のいずれでもよい。

4
3
12312312
4
121212121212
7
321312312312121212121321
7
321312312312121312121321

NO
YES
NO
YES

### 制約 - $ 1\ \le\ T\ \le\ 5\ \cdot\ 10^4 $ - $ 3\ \le\ N\ \le\ 2\ \cdot\ 10^5 $ - $ S $ は文字 `1`, `2`, `3` からなる長さ $ 4N-4 $ の文字列である。 - $ 1\ \le\ i\ \le\ 4N-5 $ のとき $ S_i\ \neq\ S_{i+1} $ であり、また $ S_{4N-4}\ \neq\ S_1 $ である。 - 各入力ファイル内の $ N $ の総和は $ 2\cdot\ 10^5 $ を超えない。 - 入力中のすべての数は整数である。 ### Sample Explanation 1 一つ目と三つ目のテストケースでは、盤面の残りを意図通りに塗る方法がないことが示せます。二つ目と四つ目のテストケースで盤面の残りを意図通りに塗る方法を以下に示します。