#agc061b. [agc061_b]Summation By Construction

[agc061_b]Summation By Construction

问题描述

左侧有 NN 个顶点 v1,,vNv_1, \ldots, v_N,右侧有 N+1N + 1 个顶点 u1,,uN+1u_1, \ldots, u_{N + 1} 的图。每个顶点 viv_i (1iN1 \leq i \leq N) 都与每个顶点 uju_j (1jN+11 \leq j \leq N + 1) 相连,即图包含 N(N+1)N(N + 1) 条边。

我们用 NN 种颜色 1,,N1, \ldots, N 对每条边进行着色。一个合适的着色应满足以下要求:对于每个 k=1,,Nk = 1, \ldots, N,颜色为 kk 的边恰好有 2k2k 条,并且这些边构成一条简单路径。

具体地,对于每个 k=1,,Nk = 1, \ldots, N,应存在一序列不同的顶点 w0,,w2kw_0, \ldots, w_{2k},使得以下条件都满足:

  • 对于每个 i=0,,2k1i = 0, \ldots, 2k - 1,顶点 wiw_iwi+1w_{i + 1} 之间有一条颜色为 kk 的边,
  • 不存在其他颜色为 kk 的边。

找到任意一个合适的着色方案,如果不存在合适的着色方案,则确定不存在。

对于每个输入文件,解决 TT 个测试用例。

约束条件

  • 1T1001 \leq T \leq 100
  • 1N1001 \leq N \leq 100

输入

从标准输入中按以下格式给出输入:

TT case1case_1 case2case_2 \vdots caseTcase_T

每个测试用例的格式如下:

NN

输出

对于每个测试用例,如果不存在合适的着色方案,则输出 No。否则,按以下格式输出一个合适的着色方案的描述:

Yes C1,1C_{1, 1} C1,2C_{1, 2} \ldots C1,N+1C_{1, N + 1} \vdots CN,1C_{N, 1} CN,2C_{N, 2} \ldots CN,N+1C_{N, N + 1}

这里,Ci,jC_{i, j} 表示 viv_iuju_j 之间的边的颜色。

如果有多个合适的着色方案,输出其中任意一个即可。


示例输入 1

2
1
2

示例输出 1

Yes
1 1
No