分数: 900 点
问题陈述
给你正整数 N 和 K.
有一个完整的二分图 G 与 N 顶点 l_1, l_2, \ldots, l_N 在左边, N 顶点 r_1, r_2, \ldots, r_N 在右边。它有 N^2 边缘;对于每个 (i, j)\ (1\leq i\leq N, 1\leq j\leq N),顶点之间有一条无向边 l_i 和 r_j.
确定是否存在在之间写入整数的方法 1 和 N^2,包含在内,在每个边缘 G (其中 N^2 写入的整数都是不同的),因此以下问题的答案是 K,如果存在这种方式,请找到一种。
在图表上的所有行走中 G,我们称之为散步 好 如果写在遍历的边上的数字序列(按照遍历的顺序)严格递增。
找到一次良好行走中包含的最大边数。
T 给出了测试用例;解决它们中的每一个。
什么是散步?
在图上行走 G 是一个序列 k 顶点和 k-1 边缘交替排列, (v_1 ,e_1 ,v_2 ,\ldots,v_{k−1} ,e_{k−1} ,v_k) (其中 k 是一个正整数),这样边 e_i 连接顶点 每个输入中的 v_i 和 v_{i+1}.约束
- 1\leq T\leq 3000
- 1\leq N\leq 700
- 1\leq K\leq N^2
- 总和 N^2 最多为 5\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N K
输出
输出以下问题的答案 \mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T 按以下格式顺序排列。
如果不存在有效的写入方式,则输出 No.
如果存在有效的方法,让 A_{i,j} 是写在连接顶点的边上的整数 l_i 和 r_j,
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,1},\ldots,A_{1,N},A_{2,1},\ldots,A_{2,N},\ldots,A_{N,1},\ldots,A_{N,N}) 必须是以下排列 (1,2,\ldots,N^2).
如果存在多个解决方案,则将接受其中任何一个。
示例输入 1
3 2 1 2 3 3 5
示例输出 1
No Yes 1 2 3 4 Yes 2 9 7 4 5 6 1 8 3
对于第一个测试用例,不存在有效的编写方式。
对于第二个测试用例,包含三个边的良好行走是 r_1 \xrightarrow{1} l_1 \xrightarrow{2}r_2\xrightarrow{4}l_2。没有好的步行包含四个或更多边缘,因此此输出满足条件。
对于第三个测试用例,包含五个边的良好行走是 l_1 \xrightarrow{2} r_1 \xrightarrow{4}l_2\xrightarrow{6}r_3 \xrightarrow{7} l_1 \xrightarrow{9} r_2。没有好的行走包含六个或更多边,因此此输出满足条件。
