Island Nations
In the turbulent feudal era, the once-flourishing island nation of ByteLandia was engulfed in conflict. Two powerful barons were vying for control over the entire island, resulting in each city being governed by one of these rulers. Traditionally, some cities are linked by two-way roads. The barons harbor a deep animosity towards each other and strive to create as much disruption as possible. Specifically, traveling on a road that connects cities ruled by different barons incurs a toll of one ByteLandian ruble. Moreover, there is an additional toll for departing from cities with even numbers.
Programmer Vasya resides in city number 1. With the onset of summer, he plans to journey to city N for the All-ByteLandian programmers' gathering. Naturally, he aims to minimize his travel expenses, and you are tasked with assisting him as always.
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 100000) — representing the number of cities and the number of roads, respectively.
The following line provides information about the cities — n integers, either 1 or 2, indicating which baron controls each city.
The subsequent m lines contain pairs of integers a and b (1 ≤ a, b ≤ n, a ≠ b). Each pair signifies the existence of a road between city a and city b. In ByteLandia, roads can be traveled in both directions.
Output
If there is no feasible path, output the single word impossible. Otherwise, on the first line, write the minimum cost and the number of cities visited, and on the second line, list these cities in the order they are visited. If there are multiple paths with the same minimal cost, output any one of them.