分数: 700 点
问题陈述
给你一个整数序列 Y=(Y_1,Y_2,\ldots,Y_N) 长度 N 其中每个元素位于 1 和 N 包括在内。
判断是否存在 N \times 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
考虑第一个测试用例。
可以验证的是 A 满足所有条件。除此之外,例如下面的 A 也将被接受:
1 3 2 3 2 1 2 1 3