← 返回题目列表

AtCoder · stpc2025_2_a

A. 各种根源

中文机器翻译题面 查看原题

配点 : 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 得到一棵无标签有根树,该无标签树满足条件。