Island Nations#1938
In the turbulent feudal era, the once-great island nation of ByteLandia was ruled by two powerful barons, each controlling some of the cities. Some cities are connected by bidirectional roads. To travel on a road connecting cities controlled by different barons, a toll of one ByteLandian ruble is required. Additionally, a double toll is charged for departing from cities with even numbers.
Programmer Vasya lives in city number . With the arrival of summer, he plans to travel to city for the ByteLandian Programmers' Gathering. He wants to spend as little money as possible on this trip, and needs your help.
The first line contains two integers and (1 \leq n, m \leq 100000) — the number of cities and the number of roads.
The next line contains integers: or — indicating which baron controls each city.
Then follow lines, each containing two integers and (1 \leq a, b \leq n, a \neq b), specifying a road between cities and . All roads are bidirectional.
If there is no possible route, output the single word impossible. Otherwise, output on the first line the minimum cost and the number of cities visited. On the second line, output the cities visited in order. If more than one minimal-cost path exists, output any of them.
Example 1