/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 900 点
問題文
正整数 N, K が与えられます．
左側に N 個の頂点 l_1, l_2, …, l_N，右側に N 個の頂点 r_1, r_2, …, r_N を持つ完全二部グラフ G があります．辺の本数は N^2 であり，各 (i, j)\ (1\leq i\leq N, 1\leq j\leq N) に対して頂点 l_i と頂点 r_j の間に無向辺が 1 つあります．
G の各辺に 1 以上 N^2 以下の整数を書き込む（ただし，書き込む N^2 個の整数は相異なるようにする）方法であって，以下の問題の答えが K になるようなものが存在するかどうか判定し，存在するならば書き込み方を一つ求めてください．
グラフ G 上のウォークのうち，通過した辺に書かれた数を通過順に並べた列が狭義単調増加となるものを良いウォークと呼びます．
良いウォークに含まれる辺の本数の最大値を求めてください．
T 個のテストケースが与えられるので，それぞれについて答えを求めてください．
ウォークとは
グラフ G 上のウォークとは， k 個（k は正整数）の頂点と k−1 個の辺を交互に並べた列 (v_1 ,e_1 ,v_2 ,\ldots,v_{k−1} ,e_{k−1} ,v_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 と出力せよ．
存在する場合，頂点 l_i と頂点 r_j を結ぶ辺に書き込む整数を A_{i,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
1 つ目のテストケースについて，条件を満たす書き込み方は存在しません．
2 つ目のテストケースについて，辺を 3 本含む良いウォークとして r_1 \xrightarrow{1} l_1 \xrightarrow{2}r_2\xrightarrow{4}l_2 が存在します．辺を 4 本以上含む良いウォークは存在しないため，この出力は条件を満たします．
3 つ目のテストケースについて，辺を 5 本含む良いウォークとして l_1 \xrightarrow{2} r_1 \xrightarrow{4}l_2\xrightarrow{6}r_3 \xrightarrow{7} l_1 \xrightarrow{9} r_2 が存在します．辺を 6 本以上含む良いウォークは存在しないため，この出力は条件を満たします．
Score : 900 points
Problem Statement
You are given positive integers N and K.
There is a complete bipartite graph G with N vertices l_1, l_2, \ldots, l_N on the left and N vertices r_1, r_2, \ldots, r_N on the right. It has N^2 edges; for each (i, j)\ (1\leq i\leq N, 1\leq j\leq N), there is one undirected edge between vertices l_i and r_j.
Determine whether there exists a way to write an integer between 1 and N^2, inclusive, on each edge of G (where the N^2 integers written are all distinct) such that the answer to the following problem is K, and if such a way exists, find one.
Among all walks on graph G, we call a walk good if the sequence of numbers written on the edges traversed, in the order they are traversed, is strictly increasing.
Find the maximum number of edges contained in a good walk.
T test cases are given; solve each of them.
What is a walk?
A walk on graph G is a sequence of k vertices and k-1 edges alternately arranged, (v_1 ,e_1 ,v_2 ,\ldots,v_{k−1} ,e_{k−1} ,v_k) (where k is a positive integer), such that edge e_i connects vertices v_i and v_{i+1}.Constraints
- 1\leq T\leq 3000
- 1\leq N\leq 700
- 1\leq K\leq N^2
- The sum of N^2 in each input is at most 5\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N K
Output
Output the answers for \mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T in this order in the following format.
If no valid way of writing exists, output No.
If a valid way exists, letting A_{i,j} be the integer written on the edge connecting vertices l_i and 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}
output as above. (A_{1,1},\ldots,A_{1,N},A_{2,1},\ldots,A_{2,N},\ldots,A_{N,1},\ldots,A_{N,N}) must be a permutation of (1,2,\ldots,N^2).
If multiple solutions exist, any of them will be accepted.
Sample Input 1
3 2 1 2 3 3 5
Sample Output 1
No Yes 1 2 3 4 Yes 2 9 7 4 5 6 1 8 3
For the first test case, no valid way of writing exists.
For the second test case, a good walk containing three edges is r_1 \xrightarrow{1} l_1 \xrightarrow{2}r_2\xrightarrow{4}l_2. No good walk contains four or more edges, so this output satisfies the condition.
For the third test case, a good walk containing five edges is l_1 \xrightarrow{2} r_1 \xrightarrow{4}l_2\xrightarrow{6}r_3 \xrightarrow{7} l_1 \xrightarrow{9} r_2. No good walk contains six or more edges, so this output satisfies the condition.