Суровые феодальные времена переживала некогда великая островная страна Байтландия. За главенство над всем островом борются два самых сильных барона. Таким образом, каждый город страны контролируется одним из правителей. Как водится издревле, некоторые из городов соединены двусторонними дорогами. Бароны очень не любят друг друга и стараются делать как можно больше пакостей. В частности, теперь для того, чтобы пройти по дороге, соединяющей города различных правителей, надо заплатить пошлину --- один байтландский рубль. Кроме этого, за выезд из городов с четными номерами берется удвоенная пошлина. Программист Вася живет в городе номер \textbf{1}. С наступлением лета он собирается съездить в город \textbf{N} на Всебайтландское сборище программистов. Разумеется, он хочет затратить при этом как можно меньше денег и помочь ему здесь, как обычно, предлагается Вам. \InputFile The first line contains two integers \textbf{n} and \textbf{m} (\textbf{1} ≤ \textbf{n}, \textbf{m} ≤ \textbf{100000}) --- the number of cities and number of roads respectively. The next line gives the information about cities --- \textbf{n} numbers \textbf{1} or \textbf{2} --- which of the barons ownes the corresponding city. In the last \textbf{m} lines the pairs \textbf{a} and \textbf{b} (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{n}, \textbf{a} ≠ \textbf{b}) are written. Each pair describes the road from city \textbf{a} to city \textbf{b}. You can move along the roads in ByteLand in any direction. \OutputFile Если искомого пути не существует, выведите единственное слово \textbf{impossible}. В противном случае, в первой строке напишите минимальную стоимость и количество посещенных городов, а во вторую выведите эти города в порядке посещения. Если минимальных путей несколько, выведите любой.