Суворі феодальні часи переживала колись велика острівна країна Байтландії. За верховенство над усім островом борються два найсильніші барони. Таким чином, кожне місто країни контролюється одним із правителів. Як водиться з давніх-давен, деякі з міст з'єднані двосторонніми дорогами.

Барони дуже не люблять один одного і намагаються робити якнайбільше пакостей. Зокрема, тепер для того щоб пройти дорогою, що з'єднує міста різних правителів, треба заплатити мито - один байтландський долар. Крім цього, за виїзд із міст з парними номерами береться подвійне мито.

Програміст Вася живе у місті номер \(1\). З настанням літа він збирається з'їздити у місто \(N\) на Всебайтландське збіговисько програмістів. Зрозуміло, він хоче витратити при це якомога менше грошей і допомогти йому тут, як завжди, пропонується Вам.

Формат вхідних даних

У першому рядку вхідного файлу записано два числа \(N\) і \(M\) (\(1 \leqslant N, M \leqslant 100\,000\)) - кількість міст та кількість доріг відповідно.

У наступному рядку міститься інформація про міста - \(N\) чисел \(1\) або \(2\) - якому з баронів належить відповідне місто.

В останніх \(M\) рядках записані пари \(1 \leqslant a, b \leqslant N\), \(a \ne b\). Кожна пара означає наявність дороги з міста \(a\) до \(b\). Дорогами Байтландії можна рухатися у будь-якому напрямку.

Формат вихідних даних

Якщо шуканого шляху немає, виведіть єдине слово \(impossible\). Інакше у першому рядку напишіть мінімальну вартість та кількість відвіданих міст, а у другому виведіть ці міста в порядку відвідування. Якщо мінімальних шляхів кілька, виведіть будь-який.

Приклад вхідних даних

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

Приклад вихідних даних

0 5
1 2 3 4 7

Приклад вхідних даних

5 5
1 1 1 2 1
1 2
2 3
3 4
4 5
2 4

Приклад вихідних даних

3 5
1 2 3 4 5