Разлад Империй
(Время: 1 сек. Память: 32 Мб Сложность: 77%)
На далёком-далёком континенте расположены n городов. Между ними располагаются m дорог: каждая соединяет два различных города и позволяет перемещаться между ними в обе стороны.
На континенте представлены три империи. Каждая империя имеет в распоряжении хотя бы один город, а каждый город принадлежит одной из империй, а именно, i-й город числится в составе империи ei (империи имеют номера 1,2 и 3).
Каждая империя беспокоится, что ей скоро объявит войну какая-то одна другая империя, поэтому все империи хотят расставить армейские штабы в каких-то своих городах.
Штабы определённой империи должны быть расставлены так, чтобы независимо от того, кто враг, из каждого города этой империи существовал безопасный путь в какой-либо штаб этой империи. Путь считает безопасным, если в нём отсутствуют города, принадлежащие вражеской империи.
Каждая империя хочет расставить минимальное количество таких штабов. Помогите континенту — определите штабы для каждой империи.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа n и m — количество городов и дорог, соответственно (3 ≤ n ≤ 30 000; 0 ≤ m ≤ 105).
Вторая строка содержит n целых чисел ei — принадлежности городов к империям (1 ≤ ei ≤3).
В следующих m строках содержатся пары чисел ui и vi, означающие наличие дороги между городами ui и vi.
Выходные данные
В выходной файл OUTPUT.TXT выведите 3 строки: i-я строка должна содержать ki — минимальное количество штабов для i-й империи, а следом ki чисел — список номеров городов, в которых эти штабы следует расположить.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 4
1 2 1 3 1
1 2
2 3
3 4
4 5 | 2 1 5
1 2
1 4 |
| 2 | 8 10
1 1 1 2 2 3 3 3
5 1
5 2
5 3
6 1
6 2
6 3
6 4
7 1
7 4
8 1 | 1 3
2 4 5
2 8 6 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
