Saturday Night Fever P48762


pdf   zip

Soy Evaristo, el rey de la baraja.


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 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 sh. Assume 2 ≤ n ≤ 105. Corners are numbered starting at one.

Next comes m, the number of streets, followed by m pairs of integer numbers ai bi, giving the corners joined by the i-th street, with aibi. 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 sj giving in order the corners that he cyclically visits. There is always a street between sj and sj+1, as well as between sv and s1. Optionally, the sbire can stay in a corner for a minute or more (that is, sj+1 = sj or s1 = sv). The sbire is at s1 the very moment Évariste first arrives at s, with s1s. 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).


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
    1  3
    4 3 2
    3  3 1  1 4  4 2
    3  4 1 4


    C'est une minute, Evariste!
    Ce sont 2 minutes, Evariste!
    Ce sont 4 minutes, Evariste!
    Tu es foutu, Evariste!
    Tu es foutu, Evariste!
  • Information
    Edgar Gonzàlez
    Official solutions
    User solutions
    Vuitè Concurs de Programació de la UPC - Semifinal