← 返回题目列表

Codeforces · 980/E

E. 数字游戏

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

小组国家每年都会举办一场名为“数字游戏”的表演,全国每个地区都将派出一名参赛者。

全国有 $$$n$$$ 个区,编号从 $$$1$$$ 到 $$$n$$$,每个区都有一条路径连接到其他每个区。来自$$$i$$$区的参赛者的粉丝数量等于$$$2^i$$$。

今年,总统决定降低成本。他想从比赛中删除 $$$k$$$ 参赛者。不过,被除名的参赛者所在的区将会勃然大怒,不允许任何人穿越他们的区。

总统希望确保所有剩余参赛者都来自彼此可以到达的地区。他还希望最大限度地增加参赛选手的粉丝总数。

总统应该删除哪些参赛者?

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k < n \leq 10^6$$$) - 分别是小组中的选区数量和总统希望删除的参赛者数量。

接下来的 $$$n-1$$$ 行每行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \leq a, b \leq n$$$, $$$a \ne b$$$),描述连接全国两个不同地区 $$$a$$$ 和 $$$b$$$ 的道路。保证每两个区域之间恰好有一条路径。

输出

打印 $$$k$$$ 以空格分隔的整数:应删除参赛者的区号,按区号升序排列。

示例

输入 #1

6 3
2 1
2 6
4 2
5 6
2 3

输出 #1

1 3 4

输入 #2

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

输出 #2

1 3 4 5

注意

在第一个示例中,最大可能的粉丝总数为 $$$2^2 + 2^5 + 2^6 = 100$$$。我们可以通过剔除1、3、4区的参赛者来实现。