最近,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