Суровые феодальные времена переживала некогда великая островная страна Байтландия. За главенство над всем островом борются два самых сильных барона. Таким образом, каждый город страны контролируется одним из правителей. Как водится издревле, некоторые из городов соединены двусторонними дорогами. Бароны очень не любят друг друга и стараются делать как можно больше пакостей. В частности, теперь для того, чтобы пройти по дороге, соединяющей города различных правителей, надо заплатить пошлину --- один байтландский рубль. Кроме этого, за выезд из городов с четными номерами берется удвоенная пошлина. Программист Вася живет в городе номер \textbf{1}. С наступлением лета он собирается съездить в город \textbf{n} на Всебайтландское сборище программистов. Разумеется, он хочет затратить при этом как можно меньше денег и помочь ему здесь, как обычно, предлагается Вам. \InputFile В первой строке записано два числа \textbf{n} и \textbf{m} (\textbf{1} ≤ \textbf{n}, \textbf{m} ≤ \textbf{100000}) --- количество городов и количество дорог соответственно. В следующий строке содержится информация о городах --- \textbf{n} чисел \textbf{1} или \textbf{2} --- какому из баронов принадлежит соответствующий город. В последних \textbf{m} строках записаны пары \textbf{a} и \textbf{b} (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{n}, \textbf{a} ≠ \textbf{b}). Каждая пара означает наличие дороги из города \textbf{a} в город \textbf{b}. По дорогам Байтландии можно двигаться в любом направлении. \OutputFile Если искомого пути не существует, выведите единственное слово \textbf{impossible}. В противном случае, в первой строке напишите минимальную стоимость и количество посещенных городов, а во вторую выведите эти города в порядке посещения. Если минимальных путей несколько, выведите любой.