← 返回题目列表

Codeforces · 1297/E

E. 林地现代化

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

Treeland 由 $$$n$$$ 城市和连接成对城市的 $$$n-1$$$ 双向道路组成。从每个城市出发,您只需通过道路即可到达其他每个城市。你是对的,这个国家的城市和道路系统形成了一棵无向的树。

政府宣布了一些城市的城市基础设施现代化计划。您已被分配选择满足以下要求的城市 $$$S$$$ 的任意子集进行升级(可能是所有城市):

- 城市子集必须是“连通”的,也就是说,从子集 $$$S$$$ 中的任何城市,您可以通过道路到达子集 $$$S$$$ 中的任何其他城市,只能通过来自 $$$S$$$ 的城市,
- $$$S$$$ 中的“死胡同”数量必须等于给定数量 $$$k$$$。如果某个城市是 $$$S$$$ 中唯一的城市,或者与 $$$S$$$ 中的另一个城市完全相连,则该城市是“死胡同”。

这显示了为给定配置选择 $$$S$$$(蓝色顶点)和 $$$k=4$$$ 的可能方法之一。死胡同是数字为 $$$1$$$、$$$4$$$、$$$6$$$ 和 $$$7$$$ 的顶点。

帮助 Treeland 升级其城市。找到任何可能的子集 $$$S$$$ 或确定这样的子集不存在。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。接下来是测试用例本身。

每个测试用例都以包含两个整数 $$$n$$$ 和 $$$k$$$ 的行开头 ($$$2 \le n \le 3 \cdot 10^5$$$, $$$1 \le k \le n$$$) — Treeland 中的城市数量以及子集 $$$S$$$ 中所需的“死胡同”城市数量。

接下来是带有道路描述的 $$$n-1$$$ 行。每条道路由两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$; $$$x \ne y$$$) 给出 - 由这条道路连接的城市的编号。我们保证您可以从每个城市到达任何其他城市,只需通过道路即可。

输入中所有测试用例的 $$$n$$$ 值的总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印“是”或“否”(在任何情况下,上限或下限),具体取决于答案是否存在。如果答案存在,则打印一个整数 $$$m$$$ ($$$1 \le m \le n$$$) — 找到的子集中的城市数量。然后打印 $$$m$$$ 从 $$$1$$$ 到 $$$n$$$ 的不同数字 — 找到的子集中的城市编号。城市号码可以按任何顺序打印。如果有多个答案,请打印其中任何一个。

示例

输入 #1

4
10 4
4 5
5 2
2 1
1 3
1 9
9 10
2 7
7 8
5 6
4 3
1 2
2 3
3 4
5 3
1 2
1 3
1 4
1 5
4 1
1 2
2 4
2 3

输出 #1

Yes
9
1 2 4 5 6 7 8 9 10 
No
Yes
4
1 3 4 5 
Yes
1
4