| Codeforces Round 408 (Div. 2) |
|---|
| Закончено |
Инзейн наконец-то нашел Зейна, и у них еще много денег! Поэтому они решили создать собственную страну.
Правление страной — непростая задача. Бандиты и террористы постоянно пытаются разрушить покой. Чтобы бороться с этим, Зейн и Инзейн разработали следующее правило: от каждого города должно быть возможно достичь пост полиции, проехав не более d километров по дорогам.
В стране n городов, пронумерованных от 1 до n, соединенных n - 1 дорогами. Все дороги имею длину 1 километр. Возможно добраться от любого города до любого другого, используя эти дороги. Кроме того, есть k постов полиции, расположенных в некоторых городах. Расположение постов полиции удовлетворяет закону, описанному выше. Заметьте, что некоторые посты могут быть расположены в одном и том же городе.
Однако, Зейн считает, что n - 1 дорога это слишком много. Страна испытывает финансовый кризис, поэтому необходимо закрыть как можно больше дорог.
Помогите Зейну определить максимальное число дорог, которое можно закрыть, не нарушая закон. Кроме того, найдите эти дороги.
Первая строка содержит три целых числа n, k и d (2 ≤ n ≤ 3·105, 1 ≤ k ≤ 3·105, 0 ≤ d ≤ n - 1) — число городов, число постов полиции, ограничение на расстояние в законе, соответственно.
Вторая строка содержит k целых чисел p1, p2, ..., pk (1 ≤ pi ≤ n) — города, в которых расположены посты полиции.
i-я из следующих n - 1 строк содержит два целых числа ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — города, непосредственно соединенные дорогой i.
Гарантируется, что возможно добраться от любого города до любого другого, используя эти дороги. Кроме того, от любого города можно добраться до поста полиции, проехав не более d километров.
В первой строке выведите одно целое число s, означающее максимальное число дорог, которое можно закрыть.
Во второй строке выведите s различных чисел — номера дорог, для которых это верно.
Если ответов несколько, выведите любой из них.
6 2 4
1 6
1 2
2 3
3 4
4 5
5 6
1
5
6 3 2
1 5 6
1 2
1 3
1 4
1 5
5 6
2
4 5
Во втором примере, если закрыть дорогу номер 5, то от всех городов по-прежнему можно будет достичь пост полиции, проехав не более k = 4 километров.
Во втором примере, несмотря на то, что множество дорог, которые можно закрыть, единственно, вы можете вывести 4 5 или 5 4 во второй строке.
