配点 : 100 点
問題文
正整数 N,K 给出。N 无标号树 T 并且,T 的 1 存在这样一种树,使得以顶点为根所得到的无标号有根树恰好有 K 种,判定是否存在这样的树;如果存在,请输出其中一种。
Q 给定个测试用例,请分别求出每个测试用例的答案。
无标号树是指
无标号树 是指没有用于区分的纵向编号,并将作为图同构的树视为相同的树。无标号树 G, H 的顶点集合分别 V(G), V(H) 记为。
2 个无标号树 G, H 满足以下条件的全双射 \phi : V(G) \to V(H) 当且仅当存在。
- 任何 关于 2 頂点 u, v \in V(G) 对于,边 uv 是 如果大于 G 存在于中,并且边 \phi(u)\phi(v) 是 如果大于 H 存在于中是等价的。
所谓无标号有根树是
无标号树 T , 定义为不包含在T 具有……的上限 r 的 根 将其设为能够与其他顶点区分开的无标号有根树 (T, r) 称为。2 个无标号有根树 (G, a), (H, b) 满足以下条件的全双射 \phi : V(G) \to V(H) 当且仅当存在。
- \phi(a) = b 。
- 任何 关于 2 頂点 u, v \in V(G) 对于,边 uv 是 如果大于 G 存在于中,并且边 \phi(u)\phi(v) 是 如果大于 H 存在于中是等价的。
制約
- 所有输入均为整数
- 1 \le Q \le 1000
- 1 \le K \le N \le 1000
- 1 输入中的所有测试用例 N 总和为 2000 以下
部分点
额外的否定 N \le 5 在正确回答满足……的数据集时 10 点。 如果您正确回答
入力
输入按以下格式给出。
Q
\text{case}_1
\text{case}_2
\vdots
\text{case}_Q
在这里, 它代表第\text{case}_i 是 i 第个测试用例,输入格式如下。
N K
出力
对于每个测试用例,请按以下格式输出。
满足题面条件的无标号树 T 不存在时,No 输出。
满足题目条件的无标签树 T 存在时,T 按各自的顺序给的顶点 1,2,\cdots,N 编号,T 将的边按以下格式输出。
Yes
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
在这里, 它代表第u_i\ v_i 是 T 的 i 第条边的上端 u_i 和顶点 连接 v_i 表示连接。
入力例 1
2 4 2 5 1
出力例 1
Yes 1 2 1 3 1 4 No
1 在第个测试用例中,4 输出了顶点的星形图。
以黑色顶点为根来看,上排的 3 个无标号有根树都视为相同。
此外,下排的无标号有根树与其他 3 个无标号有根树视为不同,因此通过这棵无标号树可以构造出 2 种无标号有根树。因此,这棵无标号树满足条件。

此外,由于可以采用任意编号方式,因此即使编号使得边集合为 \lbrace (3,4),(3,2),(3,1) \rbrace 也可以判定为正确答案。
2 在第个测试用例中,不存在满足条件的无标号树。
这个输入示例满足部分分的否定条件。
入力例 2
1 7 3
出力例 2
Yes 1 2 1 3 2 4 2 5 3 6 3 7
1 在第二个测试用例中,输出如下所示的未标记树。
在这棵无标签树中,无论选择哪个相同颜色的顶点作为根,都会创建相同的无标签有根树。
因此,3 得到一棵无标签有根树,该无标签树满足条件。
