Альт — планета в галактике «Энкор». Люди управляют этой планетой, но по некоторым причинам здесь нет собак, на их планете. Поэтому люди в депрессии и грустят. Рик и Морти вселенские филантрописты и они хотят сделать людей на планете Альт счастливыми.
Альт имеет n городов пронумерованных от 1 до n и n - 1 двунаправленных дорог, пронумерованных от 1 до n - 1. От любого города до любого можно доехать используя эти дороги.
На Альте есть два типа людей:
- Стражи. Страж живет в доме вдоль дороги и охраняет дорогу.
- Граждане. Гражданин живет дома, внутри города, и работает в офисе, в другом городе.
Каждый человек на Альте является либо стражем либо гражданином. Вдоль каждой дороги живет один страж.
Рик и Морти обратились ко всем людям на Альте, и вот что они получили:
- m граждан живет на Альте.
- Гражданин номер i живет в городе номер 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.
Примечание
Карта Альта для первого тестового примера (числа, написанные на дорогах, это их номера):
Карта Альта для второго тестового примера (числа, написанные на дорогах, это их номера):
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
2 4
3 4
1 4
2 4
2 1
2 4
1 2
2 3
|
3
1 5
2 3 1
|
|
2
|
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
|