In this editorial, we consider everything as \(0\)-indexed.

If there exists \(i\) satisfying \(Y_{Y_i} \neq i\), the answer is No. Hereafter, we consider other cases.

We call an \(N \times N\) integer matrix \(A\) satisfying all of the following conditions a good matrix.

• \(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)\)

First, if \(A\) is a good matrix and \(P\) is a permutation of \((0,1,\ldots,N-1)\), then the \(N \times N\) integer matrix \(B\) defined by \(B_{i,j}=A_{P_i,P_j}\) is also a good matrix. \(\ldots (\star)\)

Proof:

The first condition is obvious.

The second condition follows from \(B_{i,j}=A_{P_i,P_j}=A_{P_j,P_i}=B_{j,i}\).

The third condition can be rephrased as \( 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)\), and from this form we have \(B_{i,j_1} = A_{P_i,P_{j_1}} \neq A_{P_i,P_{j_2}} = B_{i,j_2}\), so it follows.

From this property, if we can construct \(B\) such that the number of \(i\) satisfying \(Y_i=i\) matches the number of \(i\) satisfying \(B_{i,i}=1\), then we can construct \(A\) satisfying all conditions.

1. When \(N\) is odd

Let \(X_k^c\) be the integer satisfying \(A_{k,X_k^c}=c\) (this value is uniquely determined). Then, \(X^c=(X_1^c,X_2^c,\ldots,X_N^c)\) must satisfy \(X_{X_k^c}^c=k\). From this, for each \(c\), the integer \(c\) must be included at least once on the diagonal of \(A\), so we know that integers from \(1\) to \(N\) are included exactly once each on the diagonal. Therefore, if there are multiple \(i\) satisfying \(Y_{Y_i} = i\), the answer is also No.

Conversely, the answer is Yes in all other cases. This is because by using \((\star)\) on the good matrix \(B\) defined by \(B_{i,j}=(i+j) \bmod N+1\), we can construct a solution.

2. When \(N\) is even

Let \(v\) be the number of \(i\) satisfying \(Y_i=i\) (this number is always even).

From \((\star)\), it suffices to construct a good matrix \(B\) where the number of \(i\) satisfying \(B_{i,i}=i\) is \(v\). And this can be constructed by the following procedure:

First, construct \(B\) such that \(B_{i,i}=1\) holds for all \(i\) using the round-robin method as follows:

• Set \(B_{i,i}=1\).
• Let \(\displaystyle S=\left(0,2,4,\ldots,N-2\right),T=\left(1,3,5,\ldots,N-1\right)\).
• For \(C=2,3,\ldots,N\), perform the following operation:
  • For \(\displaystyle i=0,1,\ldots,\frac{N}2-1\), set \(B_{S_i,T_i}=C\).
  • Fix only \(S_0\) and rotate. That is, simultaneously replace \(S,T\) with \((S_0,S_2,S_3,\ldots,S_{N-1},T_{N-1}),(S_1,T_0,T_1,\ldots,T_{N-2})\), respectively.

For example, when \(N=8\), it becomes as follows:

12384756
21653874
36127548
85216437
43761285
78542163
57438612
64875321

In \(B\) constructed this way, the \(2\times 2\) matrix obtained by extracting only rows \(2j,2j+1\) and columns \(2j,2j+1\) for each \(j\) are all \(\displaystyle \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}\). Therefore, by changing some of these to \(\displaystyle \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}\), we can construct \(B\) where the number of \(i\) satisfying \(B_{i,i}=1\) is exactly \(v\).

Then, by applying an appropriate \(P\) to this \(B\), we can construct a solution.

By implementing the above appropriately, we can solve this problem. The time complexity is \(O(N^2)\) per test case.