E. Разлад Империй
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На далёком-далёком континенте расположены $$$n$$$ городов. Между ними располагаются $$$m$$$ дорог: каждая соединяет два различных города и позволяет перемещаться между ними в обе стороны.

На континенте представлены три империи. Каждая империя имеет в распоряжении хотя бы один город, а каждый город принадлежит одной из империй, а именно, $$$i$$$-й город числится в составе империи $$$e_i$$$ (империи имеют номера 1,2 и 3).

Каждая империя беспокоится, что ей скоро объявит войну какая-то одна другая империя, поэтому все империи хотят расставить армейские штабы в каких-то своих городах.

Штабы определённой империи должны быть расставлены так, чтобы независимо от того, кто враг, из каждого города этой империи существовал безопасный путь в какой-либо штаб этой империи. Путь считает безопасным, если в нём отсутствуют города, принадлежащие вражеской империи.

Каждая империя хочет расставить минимальное количество таких штабов. Помогите континенту — определите штабы для каждой империи.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ — количество городов и дорог, соответственно ($$$3 \leq n \leq 30\,000$$$; $$$0 \leq m \leq 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$e_i$$$ — принадлежности городов к империям ($$$1 \leq e_i \leq 3$$$).

В следующих $$$m$$$ строках содержатся пары чисел $$$v_i$$$ и $$$t_i$$$, означающие наличие дороги между городами $$$v_i$$$ и $$$t_i$$$.

Выходные данные

Выведите 3 строки: $$$i$$$-я строка должна содержать $$$k_i$$$ — минимальное количество штабов для $$$i$$$-й империи, а следом $$$k_i$$$ чисел — список номеров городов, в которых эти штабы следует расположить.

Примеры
Входные данные
5 4
1 2 1 3 1
1 2
2 3
3 4
4 5
Выходные данные
2 1 5
1 2
1 4
Входные данные
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