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):

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 \ne y$ . Each case ends with the initial positions $A$ and $I$ of Anna and Ivet, respectively, with $A \ne I$ . Assume $2 \le n \le 1000$ , $n - 1 \le m \le 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