AT_agc077_b [AGC077B] Long Increasing Walk

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} $ .

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 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 Explanation 1 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.  ### 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.