Missing keys (1) P74715

After watching the news, Fulanito is worried that his (small and windowless) flat might get squatted. Consequently, he bought an extra-safe door lock (by the same company that sponsored the news) that requires d different keys to be opened.

Today, when Fulanito was going out, he realized that he had a hole in his pocket and that all of his keys dropped during his walk! Now the keys might be scattered all around the city, and he will have to collect them all individually if he wants to return home.

Consider that the city is an undirected graph with n nodes (street crosses) and m edges (streets), and that it takes one minute to traverse any of the streets. Given the location of each of the d keys, what is the minimum time that Fulanito needs to get home with all of his keys? Assume that Fulanito is initially at node 0, that his home is at node n−1, and that it takes no time to collect any keys at any given location.

Input

Input consists of several cases, each one with n, m, m pairs x y to indicate an edge between x and y, d, and the d locations of the keys. Assume 2 ≤ n ≤ 5 · 10⁴, 0 ≤ m ≤ 5n, 0 ≤ d ≤ 15, that vertices are numbered from 0 to n−1, and that there are no multi-edges or self-loops.

Output

For every case, print the minimum number of minutes to get home with all the keys. Print “impossible” if there is no way of doing so.