Островні держави
Сурові феодальні часи переживала колись велика острівна держава Байтландія. За володарювання над усім островом борються два самих сильних барони. Таким чином, кожне місто країни контролюється одним з правителів. Як водиться з давніх-давен, деякі з міст з'єднані двохсторонніми дорогами. Барони дуже не люблять один одного і намагааються робити якомога більше пакостей. Зокрема, тепер для того, щоб пройти по дорозі, яка з'єднує міста різних правителів, потрібно заплатити пошлину — один байтландський рубль. Крім того, за виїзд з міст з парними номерами береться подвійна пошлина.
Програміст Вася живе у місті номер 1. З настанням літа він збирається з'їздити у місто N на Всебайтландське зборище програмістів. Зрозуміло, він хоче потратити при цьому якомога менше грошей і допомогти йому тут, як завжди, пропонується Вам.
Вхідні дані
У першому рядку записано два числа n та m (1 ≤ n, m ≤ 100000) — кількість міст та кількість доріг відповідно.
У наступному рядку міститься інформація про міста — n чисел 1 або 2 — якому з баронів належить відповідне місто.
В останніх m рядках записані пары a та b (1 ≤ a, b ≤ n, a ≠ b). Кожна пара позначає наявність дороги з міста a у місто b. По дорогам Байтландії можна рухатись у довільному напрямку.
Вихідні дані
Якщо шуканого шляху не існує, виведіть єдине слово impossible. У протилежному випадку, у першому рядку напишіть мінімальну вартість та кількість відвіданих міст, а у другому виведіть ці міста у порядку відвідування. Якщо мінімальних шляхів декілька, виведіть довільний.