← 返回题目列表

Codeforces · 440/D

D. 伯兰联邦化

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

最近,Berland 越来越频繁地面临联邦化请求。支持者提议将国家分为不同的州。此外,他们要求有一个州恰好包含 k 个城镇。

目前,贝尔兰有n个城镇,其中一些城镇通过双边公路相连。 Berland 只有 n - 1 条道路。从首都可以到达任何城市,即路网形成树状。

道路部担心改革后那些连接不同州城镇的道路会带来很多麻烦。

您的任务是制定一项计划,将国家划分为多个州,以便:

- 每个州都是相连的,即对于每个州,可以使用其道路(即连接州城镇的道路)从任何城镇到达任何其他城镇,
- 有一个州由 k 个城市组成,
- 连接不同州的道路数量最少。

输入

第一行包含整数 n, k (1 ≤ k ≤ n ≤ 400)。然后沿着 n - 1 行,每行描述 Berland 的一条路。道路以整数对形式给出 xi, yi (1 ≤ xi, yi ≤ n; xi ≠ yi) — 由道路连接的城镇数量。假设城镇编号为 1 到 n。

输出

第一行打印所需的最小“问题”道路数 t。然后打印 t 个整数的序列——它们在找到的除法中的索引。道路按照输入中的顺序从 1 开始编号。如果有多种可能的解决方案,请打印其中任何一个。

如果解表明根本不存在“问题”道路,则打印单个整数 0 并将第二行留空或根本不打印。

示例

输入 #1

5 2
1 2
2 3
3 4
4 5

输出 #1

1
2

输入 #2

5 3
1 2
1 3
1 4
1 5

输出 #2

2
3 4

输入 #3

1 1

输出 #3

0