Инзейн наконец-то нашел Зейна, и у них еще много денег! Поэтому они решили создать собственную страну.
Правление страной — непростая задача. Бандиты и террористы постоянно пытаются разрушить покой. Чтобы бороться с этим, Зейн и Инзейн разработали следующее правило: от каждого города должно быть возможно достичь пост полиции, проехав не более d километров по дорогам.
В стране n городов, пронумерованных от 1 до n, соединенных n - 1 дорогами. Все дороги имею длину 1 километр. Возможно добраться от любого города до любого другого, используя эти дороги. Кроме того, есть k постов полиции, расположенных в некоторых городах. Расположение постов полиции удовлетворяет закону, описанному выше. Заметьте, что некоторые посты могут быть расположены в одном и том же городе.
Однако, Зейн считает, что n - 1 дорога это слишком много. Страна испытывает финансовый кризис, поэтому необходимо закрыть как можно больше дорог.
Помогите Зейну определить максимальное число дорог, которое можно закрыть, не нарушая закон. Кроме того, найдите эти дороги.
Выходные данные
В первой строке выведите одно целое число s, означающее максимальное число дорог, которое можно закрыть.
Во второй строке выведите s различных чисел — номера дорог, для которых это верно.
Если ответов несколько, выведите любой из них.
Примечание
Во втором примере, если закрыть дорогу номер 5, то от всех городов по-прежнему можно будет достичь пост полиции, проехав не более k = 4 километров.
Во втором примере, несмотря на то, что множество дорог, которые можно закрыть, единственно, вы можете вывести 4 5 или 5 4 во второй строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2 4
1 6
1 2
2 3
3 4
4 5
5 6
|
1
5
|
|
2
|
6 3 2
1 5 6
1 2
1 3
1 4
1 5
5 6
|
2
4 5
|