| Codeforces Round 406 (Div. 1) |
|---|
| Закончено |
Альт — планета в галактике «Энкор». Люди управляют этой планетой, но по некоторым причинам здесь нет собак, на их планете. Поэтому люди в депрессии и грустят. Рик и Морти вселенские филантрописты и они хотят сделать людей на планете Альт счастливыми.
Альт имеет n городов пронумерованных от 1 до n и n - 1 двунаправленных дорог, пронумерованных от 1 до n - 1. От любого города до любого можно доехать используя эти дороги.
На Альте есть два типа людей:
- Стражи. Страж живет в доме вдоль дороги и охраняет дорогу.
- Граждане. Гражданин живет дома, внутри города, и работает в офисе, в другом городе.
Каждый человек на Альте является либо стражем либо гражданином. Вдоль каждой дороги живет один страж.
Рик и Морти обратились ко всем людям на Альте, и вот что они получили:
- m граждан живет на Альте.
- Гражданин номер i живет в городе номер xi и работает в городе номер yi.
- Каждый день гражданин едет по дорогам вдоль кратчайшего пути от его дома на работу.
- Гражданин будет счастлив, если и только если он будет иметь щенка, или все стражи вдоль пути на его работу будут иметь щенка (он видит щенков у стражей на каждой дороге и он счастлив).
- Страж всегда счастлив.
Вам необходимо сказать Рику и Морти минимальное количество щенков необходимое, чтобы сделать всех на Альте счастливыми, и также предоставить оптимальный путь раздать щенков.
В первой строке входных данных содержатся два целых числа n и m (2 ≤ n ≤ 2 × 104, 1 ≤ m ≤ 104) — количество городов и количество граждан соответственно.
Следующие n - 1 строк содержат дороги, i-я строка содержит концы i-го ребра, v и u (1 ≤ v, u ≤ n, v ≠ u).
Следующие m строк содержат информацию о гражданах. i-я строка содержит два целых числа xi и yi (1 ≤ xi, yi ≤ n, xi ≠ yi).
В первой строке выведите целое число k — суммарное необходимое количество щенков (1 ≤ k ≤ n).
Во второй строке выведите число q — количество щенков, которых необходимо раздать гражданам, за которым следует q различных чисел a1, a2, ..., aq — номера граждан, которым необходимо раздать щенков (0 ≤ q ≤ min(m, k), 1 ≤ ai ≤ m).
В третьей строке выведите число e — количество щенков, которых необходимо раздать стражам, за которым следует e различных целых чисел b1, b2, ..., be — номера дорог, стражам которых необходимо раздать щенков (0 ≤ e ≤ min(n - 1, k), 1 ≤ bi ≤ n - 1).
Сумма q и e должна быть равна k.
4 5
2 4
3 4
1 4
2 4
2 1
2 4
1 2
2 3
3
1 5
2 3 1
4 7
3 4
1 4
2 1
4 2
4 2
2 4
1 4
2 1
3 1
4 2
3
1 6
2 2 3
Карта Альта для первого тестового примера (числа, написанные на дорогах, это их номера):
Карта Альта для второго тестового примера (числа, написанные на дорогах, это их номера):
