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^{5}.
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* ≤ 10*n*.

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*_{1}.
Optionally, the *sbire* can stay in a corner for a minute or more
(that is, *s*_{j+1} = *s*_{j} or *s*_{1} = *s*_{v}). The *sbire* is at *s*_{1}
the very moment Évariste first arrives at *s*, with *s*_{1} ≠ *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.

Public test cases

**Input**

3 1 2 3 1 2 2 3 3 1 1 3 3 1 2 3 1 2 2 3 3 1 2 3 2 6 1 6 7 1 2 2 3 3 4 4 5 5 6 2 5 3 5 3 3 4 5 3 1 2 0 1 3 4 3 2 3 3 1 1 4 4 2 3 4 1 4

**Output**

C'est une minute, Evariste! Ce sont 2 minutes, Evariste! Ce sont 4 minutes, Evariste! Tu es foutu, Evariste! Tu es foutu, Evariste!

Information

- Author
- Edgar Gonzàlez
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Vuitè Concurs de Programació de la UPC - Semifinal
- Date
- 2010-06-30