eolymp
Competitions

2011 Зимняя Школа, Харьков, День 8, День Виталия Гольдштейна

Островные государства

Суровые феодальные времена переживала некогда великая островная страна Байтландия. За главенство над всем островом борются два самых сильных барона. Таким образом, каждый город страны контролируется одним из правителей. Как водится издревле, некоторые из городов соединены двусторонними дорогами. Бароны очень не любят друг друга и стараются делать как можно больше пакостей. В частности, теперь для того, чтобы пройти по дороге, соединяющей города различных правителей, надо заплатить пошлину — один байтландский рубль. Кроме этого, за выезд из городов с четными номерами берется удвоенная пошлина.

Программист Вася живет в городе номер 1. С наступлением лета он собирается съездить в город N на Всебайтландское сборище программистов. Разумеется, он хочет затратить при этом как можно меньше денег и помочь ему здесь, как обычно, предлагается Вам.

Input

The first line contains two integers n and m (1n, m100000) — the number of cities and number of roads respectively.

The next line gives the information about cities — n numbers 1 or 2 — which of the barons ownes the corresponding city.

In the last m lines the pairs a and b (1a, bn, ab) are written. Each pair describes the road from city a to city b. You can move along the roads in ByteLand in any direction.

Output

Если искомого пути не существует, выведите единственное слово impossible. В противном случае, в первой строке напишите минимальную стоимость и количество посещенных городов, а во вторую выведите эти города в порядке посещения. Если минимальных путей несколько, выведите любой.

Time limit 2 seconds
Memory limit 256 MiB
Input example #1
7 8
1 1 1 1 2 2 1
1 2
2 5
2 3
5 4
4 3
4 7
1 6
6 7
Output example #1
0 5
1 2 3 4 7
Author Vitaly Goldstein
Source Winter School, Kharkov, 2011, Day 9