Berland Federalization

题意翻译

### 题目描述 最近，Berland 面临着越来越重的联邦化的要求。许多支持者建议将国家分成几个独立的州。此外，她们还要求有一个州恰好包含 k 个城市。 现在，Berland 有 n 个城市，有一些城市间通过双向道路连接，共有 n−1 条道路，组成树形结构。 政府害怕分离后，连接不同州的道路会惹麻烦，所以她们提出了如下要求： 每一个州是一个连通块，即每个州内部是互相连通的。 存在一个州，它恰好包含 k 个城市。 连接不同州的道路数量尽可能小。 你的任务就是想出一个方案，使得满足上述要求的同时，让连接不同州的道路数量达到最小值。 ### 输入格式 第一行包含两个正整数 $n,k(1≤k≤n≤400)$。 接下来的 n−1 行，每行描述一条道路，其中包含两个整数 $xi,yi(1≤xi≠yi≤n)$，表示有一条道路连接城市 xi 和 yi。 ### 输出格式 第一行输出一个整数，表示连接不同州的道路数量的最小值 t。 第二行输出 t 个整数，表示连接不同州的道路对应的编号 (按照输入中的顺序以 1∼n−1 给道路编号)。

题目描述

Recently, Berland faces federalization requests more and more often. The proponents propose to divide the country into separate states. Moreover, they demand that there is a state which includes exactly $ k $ towns. Currently, Berland has $ n $ towns, some pairs of them are connected by bilateral roads. Berland has only $ n-1 $ roads. You can reach any city from the capital, that is, the road network forms a tree. The Ministry of Roads fears that after the reform those roads that will connect the towns of different states will bring a lot of trouble. Your task is to come up with a plan to divide the country into states such that: - each state is connected, i.e. for each state it is possible to get from any town to any other using its roads (that is, the roads that connect the state towns), - there is a state that consisted of exactly $ k $ cities, - the number of roads that connect different states is minimum.

输入输出格式

输入格式

The first line contains integers $ n $ , $ k $ ( $ 1<=k<=n<=400 $ ). Then follow $ n-1 $ lines, each of them describes a road in Berland. The roads are given as pairs of integers $ x_{i},y_{i} $ ( $ 1<=x_{i},y_{i}<=n; x_{i}≠y_{i} $ ) — the numbers of towns connected by the road. Assume that the towns are numbered from 1 to $ n $ .

输出格式

The the first line print the required minimum number of "problem" roads $ t $ . Then print a sequence of $ t $ integers — their indices in the found division. The roads are numbered starting from 1 in the order they follow in the input. If there are multiple possible solutions, print any of them. If the solution shows that there are no "problem" roads at all, print a single integer 0 and either leave the second line empty or do not print it at all.

输入输出样例

输入样例 #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

题意翻译

### 题目描述 最近，Berland 面临着越来越重的联邦化的要求。许多支持者建议将国家分成几个独立的州。此外，她们还要求有一个州恰好包含 k 个城市。 现在，Berland 有 n 个城市，有一些城市间通过双向道路连接，共有 n−1 条道路，组成树形结构。 政府害怕分离后，连接不同州的道路会惹麻烦，所以她们提出了如下要求： 每一个州是一个连通块，即每个州内部是互相连通的。 存在一个州，它恰好包含 k 个城市。 连接不同州的道路数量尽可能小。 你的任务就是想出一个方案，使得满足上述要求的同时，让连接不同州的道路数量达到最小值。 ### 输入格式 第一行包含两个正整数 $n,k(1≤k≤n≤400)$。 接下来的 n−1 行，每行描述一条道路，其中包含两个整数 $xi,yi(1≤xi≠yi≤n)$，表示有一条道路连接城市 xi 和 yi。 ### 输出格式 第一行输出一个整数，表示连接不同州的道路数量的最小值 t。 第二行输出 t 个整数，表示连接不同州的道路对应的编号 (按照输入中的顺序以 1∼n−1 给道路编号)。