D - Symmetric Matrix Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

各要素が 1 以上 N 以下であるような長さ N の整数列 Y=(Y_1,Y_2,\ldots,Y_N) が与えられます。

以下の条件を全て満たす N 行 N 列の整数行列 A=(A_{i,j}) (1\le i , j \le N) が存在するか判定し、存在する場合は一つ求めてください。

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

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1\le T\le 5000
  • 1\le N \le 500
  • 全てのテストケースにおける N^2 の総和は 500^2 以下
  • 1\le Y_i\le N
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

N
Y_1 Y_2 \ldots Y_N

出力

各テストケースに対する答えを順に改行区切りで出力せよ。

各テストケースについて、条件を全て満たす A が存在しない場合は No を出力せよ。

そうでない場合、条件を全て満たす A を以下の形式で出力せよ。

Yes
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}

条件を全て満たす A が複数ある場合、どれを出力しても正答となる。

入力例 1

4
3
1 3 2
3
1 2 3
1
1
5
1 3 2 5 4

出力例 1

Yes
1 2 3
2 3 1
3 1 2
No
Yes
1
Yes
1 2 5 4 3
2 3 1 5 4
5 1 4 3 2
4 5 3 2 1
3 4 2 1 5

1 つ目のテストケースについて考えます。

出力例の A は条件を全て満たすことが確認できます。この他にも、例えば以下のような A を出力しても正答となります。

1 3 2
3 2 1
2 1 3

Score : 700 points

Problem Statement

You are given an integer sequence Y=(Y_1,Y_2,\ldots,Y_N) of length N where each element is between 1 and N inclusive.

Determine whether there exists an N \times N integer matrix A=(A_{i,j}) (1\le i , j \le N) that satisfies all of the following conditions, and if it exists, find one such matrix.

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

You are given T test cases; solve each of them.

Constraints

  • 1\le T\le 5000
  • 1\le N \le 500
  • The sum of N^2 over all test cases is at most 500^2.
  • 1\le Y_i\le N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N
Y_1 Y_2 \ldots Y_N

Output

Output the answers for each test case in order, separated by newlines.

For each test case, if there does not exist an A that satisfies all conditions, print No.

Otherwise, print A that satisfies all conditions in the following format:

Yes
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}

If there are multiple A that satisfy all conditions, any of them will be accepted.

Sample Input 1

4
3
1 3 2
3
1 2 3
1
1
5
1 3 2 5 4

Sample Output 1

Yes
1 2 3
2 3 1
3 1 2
No
Yes
1
Yes
1 2 5 4 3
2 3 1 5 4
5 1 4 3 2
4 5 3 2 1
3 4 2 1 5

Consider the first test case.

It can be verified that the A in the sample output satisfies all conditions. Other than this, for example, the following A will also be accepted:

1 3 2
3 2 1
2 1 3