Saturday Night Fever P48762

Soy Evaristo, el rey de la baraja.

[r]

Young Évariste Galois (i.e., the only Évariste Galois there ever was) has a busy night ahead. He has an appointment for a duel at dawn and he still has to get home and write down all his revolutionary ideas about group theory during the night. And all this while he constantly despises that lady. That’s more than enough to give you a kind of ache in your stomach…

But alas, poor Évariste! Because when he gets to his neighborhood, he finds that there is a sbire of his enemies wandering in the area, quite close to where his home is.

Given that Évariste does not want to die before the morning (being the moral at the time that death, like virginity, was something to be reserved for someone special), can you tell him if he can get home safe and sound, or if, on the contrary, this is not the case?

Input

Input consists of several cases. Every case begins with n, the number of corners in the neighborhood. Follows the corner s where Évariste is located to start with, and the corner h of Évariste’s home, with s ≠ h. Assume 2 ≤ n ≤ 10⁵. Corners are numbered starting at one.

Next comes m, the number of streets, followed by m pairs of integer numbers a_i b_i, giving the corners joined by the i-th street, with a_i ≠ b_i. The streets are two-way, all different. It ‍always takes one minute to go from one corner to the next one. Assume 0 ≤ m ≤ 10n.

Then comes v, the number of corners patrolled by the sbire, followed by v integers s_j giving in order the corners that he cyclically visits. There is always a street between s_j and s_j+1, as well as between s_v and s₁. Optionally, the sbire can stay in a corner for a minute or more (that is, s_j+1 = s_j or s₁ = s_v). The sbire is at s₁ the very moment Évariste first arrives at s, with s₁ ≠ s. Assume 1 ≤ v ≤ 10.

Évariste cannot be in a corner the same minute the sbire is there, and he cannot follow a street if the sbire is walking the same street in the opposite direction. However, Évariste can decide to stay in a corner for a minute or more (obviously, as long as the sbire does not arrive there during that time).

Output

For every case, print a single line. If Évariste can get home, report the amount of minutes, paying attention to the special case of one minute. If, by contrast, Évariste is in trouble, report the situation.