eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Островні держави

Островні держави

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

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

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

Вхідні дані

У першому рядку записано два числа n та m (1n, m100000) — кількість міст та кількість доріг відповідно.

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

В останніх m рядках записані пары a та b (1a, bn, ab). Кожна пара позначає наявність дороги з міста a у місто b. По дорогам Байтландії можна рухатись у довільному напрямку.

Вихідні дані

Якщо шуканого шляху не існує, виведіть єдине слово impossible. У протилежному випадку, у першому рядку напишіть мінімальну вартість та кількість відвіданих міст, а у другому виведіть ці міста у порядку відвідування. Якщо мінімальних шляхів декілька, виведіть довільний.

Приклад

Вхідні дані #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
Вихідні дані #1
0 5
1 2 3 4 7
Автор Віталій Гольдштейн
Джерело Зимова Школа, Харків 2011, День 9