この解説では全て 0-indexed で考えます。

\(Y_{Y_i} \neq i\) を満たす \(i\) が存在する場合の答えは No です。以降はこれ以外の場合を考えます。

以下の条件を全て満たす \(N\) 行 \(N\) 列の整数係数行列 \(A\) を 良い行列 と呼びます。

• \(1\le A_{i,j}\le N\) \((0\le i < N,0\le j< N)\)
• \(A_{i,j} = A_{j,i}\) \((0\le i < N,0\le j< N)\)
• \(A_{i,j_1} \neq A_{i,j_2}\) \((0\le i < N,0\le j_1 < j_2< N)\)

まず、 \(A\) を良い行列、 \(P\) を \((0,1,\ldots,N-1)\) の順列とすると \(B_{i,j}=A_{P_i,P_j}\) で定義される \(N\) 行 \(N\) 列の整数係数行列 \(B\) も良い行列であることが分かります。 \(\ldots (\star)\)

証明：

\(1\) つ目の条件は明らかです。

\(2\) つ目の条件は \(B_{i,j}=A_{P_i,P_j}=A_{P_j,P_i}=B_{j,i}\) より従います。

\(3\) つ目の条件は \( A_{i,j_1} \neq A_{i,j_2}\) \((0\le i< N, 0\le j_1 , j_2< N,j_1 \color{red}\neq\color{black} j_2)\) と言い換えられますが、この形から \(B_{i,j_1} = A_{P_i,P_{j_1}} \neq A_{P_i,P_{j_2}} = B_{i,j_2}\) となり従います。

この性質から、 \(Y_i=i\) を満たす \(i\) の個数と \(B_{i,i}=1\) を満たす \(i\) の個数が一致するような \(B\) を構成することができれば条件を全て満たす \(A\) が構成できることが分かります。

1. \(N\) が奇数のとき

\(X_k^c\) を \(A_{k,X_k^c}=c\) を満たす整数とします（この値は一つに定ります）。すると、\(X^c=(X_1^c,X_2^c,\ldots,X_N^c)\) は \(X_{X_k^c}^c=k\) を満たす必要があります。このことから各 \(c\) に対し整数 \(c\) は \(A\) の対角線上に \(1\) つ以上含まれる必要があるため、\(1\) 以上 \(N\) 以下の整数は対角線上にちょうど \(1\) つずつ含まれることが分かります。したがって、 \(Y_{Y_i} = i\) を満たす \(i\) が複数存在する場合も答えは No です。

逆にそれ以外の場合の答えは Yes です。なぜならば、 \(B_{i,j}=(i+j) \bmod N+1\) で定めた良い行列 \(B\) に対し \((\star)\) を用いれば解を構成できるからです。

2. \(N\) が偶数のとき

\(v\) を \(Y_i=i\) を満たす \(i\) の個数とします（この個数は必ず偶数です）。

\((\star)\) より \(B_{i,i}=i\) を満たす \(i\) の個数が \(v\) 個であるような良い行列 \(B\) が構成できれば良いです。そしてこれは以下の手順で構成できます：

まず全ての \(i\) に対し \(B_{i,i}=1\) が成り立つ \(B\) を以下のように round-robin 方式で構成します。

• \(B_{i,i}=1\) とする。
• \(\displaystyle S=\left(0,2,4,\ldots,N-2\right),T=\left(1,3,5,\ldots,N-1\right)\) とする。
• \(C=2,3,\ldots,N\) に対して以下の操作を行う：
  • \(\displaystyle i=0,1,\ldots,\frac{N}2-1\) に対し \(B_{S_i,T_i}=C\) とする。
  • \(S_0\) のみ固定して rotate する。つまり、 \(S,T\) をそれぞれ \((S_0,S_2,S_3,\ldots,S_{N-1},T_{N-1}),(S_1,T_0,T_1,\ldots,T_{N-2})\) に同時に置き換える。

例えば \(N=8\) の場合は以下のようになります：

12384756
21653874
36127548
85216437
43761285
78542163
57438612
64875321

このように構成した \(B\) は 各 \(j\) に対し \(2j,2j+1\) 行・ \(2j,2j+1\) 列のみをくり抜いた \(2\times 2\) 行列が全て \(\displaystyle \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}\) となります。したがって、これらのいくつかを \(\displaystyle \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}\) に変えることで \(B_{i,i}=1\) が成り立つ \(i\) の個数がちょうど \(v\) 個であるような \(B\) を構成できます。

あとはこの \(B\) に対し適切な \(P\) を作用させることで解を構成することができます。

以上を適切に実装することでこの問題に正答することができます。計算量は各テストケースあたり \(O(N^2)\) です。