The frog game

The frogs Anna and Ivet are jumping on the stones of a pond. Anna wants
to catch Ivet, and Ivet is trying to escape. They take turns: First,
Ivet jumps from her current stone to any neighboring stone; then Anna
does the same, and so on, until Anna and Ivet are on the same stone
(Anna wins) or until they stop playing because Ivet would always escape.

For example, consider the first situation (A indicates where Anna is, I
where Ivet is, the numbers represent stones, and the lines indicate
possible jumps):

[image] [image]

If Ivet were to jump to stone 1, Anna would catch her on the next turn.
Therefore, Ivet jumps to 6. Now Anna jumps to 1. Now Ivet must return to
where she was (staying still is not allowed when it is their turn to
move), so Anna catches her on the next turn.

By contrast, it is easy to see that Anna will never be able to catch
Ivet in the second situation, if Ivet plays well.

Input

Input consists of several cases. Each case begins with the description
of the pond, modeled as an undirected, connected graph with n vertices
and m edges. Thus, we have n, m and m pairs x y indicating an edge
between x and y, with x ≠ y. Each case ends with the initial positions A
and I of Anna and Ivet, respectively, with A ≠ I. Assume 2 ≤ n ≤ 1000,
n − 1 ≤ m ≤ 5n, that vertices are numbered from 0 to n − 1, and that
there are no repeated edges.

Output

For each case, assuming perfect play, if Anna will never catch Ivet,
print “no”. Otherwise, print the minimum number of steps until Anna
catches Ivet.

Problem information

Author: Salvador Roura
Event: Vint-i-quatrè Concurs de Programació de la UPC - Final
Date: 2026-10-07

Generation: 2026-10-07T12:55:08.279Z

© Jutge.org, 2006–2026.
https://jutge.org
