На отдыхе в Теплой Стране Вера познакомилась с симпатичным волейболистом- трактористом Петром. Турист Петр, кстати, собирается после отличного отдыха в Теплой Стране отправиться в путешествие по городам Европы. Как известно, Европа облада- ет развитой транспортной системой: в Европе есть V интересующих Петра городов и E маршрутов ночных поездов. Каждый маршрут соединяет два различных города, время в пути составляет одну ночь. Поезда по маршруту ходят в обоих направлениях.
Основной целью поездки Петра является осмотр местных достопримечательностей. Поскольку Петр — невероятно занятой человек, то он решил, что все путешествие должно занимать не более четырех дней. Петр уже многое повидал, поэтому на осмотр досто- примечательностей в каждом городе Петр тратит ровно один день. Он хочет составить наиболее практичный тур: каждый день он будет тратить на осмотр города, а каждую ночь — на переезд ночным поездом между городами. Разумеется, Петр не имеет ни ма- лейшего желания посещать один город несколько раз.
Но на этом прагматичность Петра не заканчивается: Петр, как настоящий турист, хо- чет посмотреть на самые красивые европейские достопримечательности. Он долго изучал справочники и для каждого города оценил свою ожидаемую радость от его посещения pi. Теперь он хочет найти маршрут, при котором его радость будет наибольшей. Помогите Петру найти такой маршрут.
Формат входного файла
В первой строке входных данных заданы два целых числа V и E (1 <= V, E <= 3 · 10
5 ) — количество городов и маршрутов поездов, соответственно. В следующей строке заданы V целых чисел p
i (1 <= p
i <= 10
8 ), где pi обозначает ожидаемую радость от посещения го- рода с номером i. В следующих E строках заданы описания маршрутов поездов. Каждое описание состоит из пары различных чисел ai и bi (1 <= a
i, b
i <= V ) — номеров городов, меж- ду которыми курсирует этот маршрут поезда. Гарантируется, что между каждой парой городов существует не более одного маршрута поезда.
Формат выходного файла
В первой строке выходных данных выведите число K (1 <= K <= 4) — количество горо- дов в оптимальном маршруте туриста Петра. В следующей строке выведите номера этих городов в порядке посещения. Города нумеруются начиная с единицы. Если оптимальных маршрутов несколько, выведите любой из них.
| Ввод |
Вывод |
5 4
4 2 3 1 5
1 2
2 3
3 4
4 5 |
4
2 3 4 5 |
4 3
1 2 3 4
1 2
1 3
1 4 |
3
4 1 3 |