/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
左側に N 個の頂点 v_1, \ldots, v_N、右側に N + 1 個の頂点 u_1, \ldots, u_{N + 1} を持つグラフがあります。各頂点 v_i (1 \leq i \leq N) は各頂点 u_j (1 \leq j \leq N + 1) と結ばれています。すなわち、グラフは N(N + 1) 本の辺を持ちます。
各辺を、N 種類の色 1, \ldots, N のうちいずれか一つで塗ります。k = 1, \ldots, N のいずれに対しても、色 k の辺がちょうど 2k 本あってそれらが単純パスをなすとき、塗り方を適切であるとします。
形式的には、各 k = 1, \ldots, N について相異なる頂点の列 w_0, \ldots, w_{2k} が存在して以下をすべて満たすとき、塗り方は適切です。
- 各 i = 0, \ldots, 2k - 1 について、頂点 w_i と w_{i + 1} は色 k の辺で結ばれている。
- 色 k の辺は他に存在しない。
適切な塗り方をいずれか一つ、あるいはそれが存在しないことを見出してください。
各入力ファイルについて、テストケースを T 個解いてください。
制約
- 1 \leq T \leq 100
- 1 \leq N \leq 100
入力
入力は、標準入力から以下の形式で与えられる。
T case_1 case_2 \vdots case_T
各ケースは、以下の形式である。
N
出力
それぞれのケースについて、適切な塗り方が存在しないなら、No を出力せよ。そうでないなら、以下の形式で適切な塗り方を一つ出力せよ。
Yes
C_{1, 1} C_{1, 2} \ldots C_{1, N + 1}
\vdots
C_{N, 1} C_{N, 2} \ldots C_{N, N + 1}
ここで、C_{i, j} は v_i と u_j を結ぶ辺の色である。
適切な塗り方が複数ある場合は、いずれを出力してもよい。
入力例 1
2 1 2
出力例 1
Yes 1 1 No
Score : 800 points
Problem Statement
There is a graph with N vertices v_1, \ldots, v_N on the left, and N + 1 vertices u_1, \ldots, u_{N + 1} on the right. Each vertex v_i (1 \leq i \leq N) is connected to each vertex u_j (1 \leq j \leq N + 1), that is, the graph contains N(N + 1) edges.
We color every edge with one of the N colors 1, \ldots, N. A coloring is suitable if for each k = 1, \ldots, N there are exactly 2k edges of color k, and those edges form a simple path.
Formally, for each k = 1, \ldots, N there should exist a sequence of distinct vertices w_0, \ldots, w_{2k} such that all of the following is true:
- For each i = 0, \ldots, 2k - 1, vertices w_i and w_{i + 1} are connected with an edge of color k,
- No other edges of color k exist.
Find any suitable coloring, or determine that it doesn't exist.
For each input file, solve T test cases.
Constraints
- 1 \leq T \leq 100
- 1 \leq N \leq 100
Input
Input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is in the following format:
N
Output
For each test case, if a suitable coloring does not exist, print No. Otherwise, print a suitable coloring description in the following format:
Yes
C_{1, 1} C_{1, 2} \ldots C_{1, N + 1}
\vdots
C_{N, 1} C_{N, 2} \ldots C_{N, N + 1}
Here, C_{i, j} is the color of the edge between v_i and u_j.
If there are many suitable colorings, print any of them.
Sample Input 1
2 1 2
Sample Output 1
Yes 1 1 No