AT_agc077_b [AGC077B] Long Increasing Walk

给定正整数 $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$ 之间存在一条无向边。 你需要判断是否存在一种方法，在 $G$ 的每条边上写一个 $1$ 到 $N^2$ 之间的整数（这 $N^2$ 个整数互不相同），使得下面问题的答案为 $K$，如果存在请给出一种方案。 > 在所有 $G$ 上的步行中，若遍历过的边上所写的数字序列严格递增，则称该步行为“优秀步行”。 > > 请找出优秀步行所能经过的最大边数。 给出 $T$ 组测试数据，请分别解决每组数据。 步行的定义如下：在图 $G$ 上的步行是一个交替排列的顶点和边的序列 $(v_1 ​ ,e_1 ​ ,v_2 ​ ,\ldots,v_{k−1} ​ ,e_{k−1} ​ ,v_k)$（其中 $k$ 是正整数），要求每条边 $e_i$ 都应连接顶点 $v_i$ 和 $v_{i+1}$。

输入以标准输入给出，格式如下： > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 每组测试数据格式如下： > $N\ K$

请依次输出每个测试用例的答案。 如果不存在合法的标号方案，输出 `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$ 到 $N^2$ 的一个排列。 若有多种方案，输出任意一种均可。

### 样例解释 1 对于第一个测试用例，不存在合法的标号方案。 对于第二个测试用例，一个包含三条边的优秀步行为 $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$。不存在包含六条边的优秀步行，因此这个输出是合法的。  ### 数据范围 - $1\leq T\leq 3000$ - $1\leq N\leq 700$ - $1\leq K\leq N^2$ - 所有输入中的 $N^2$ 之和不超过 $5\times 10^5$。 - 所有输入值均为整数。 由 ChatGPT 5 翻译