P2302 loidc, Run

loidc abducted a young girl on the road. (Isn't he a philosopher!?)

Now he is being hunted by cony. loidc fled into a maze, and cony has followed him there. The maze consists of cells numbered from $1$ to $n$. Some pairs of distinct cells are adjacent; the set of adjacencies is given. A person in the maze may either stay where they are or move to an adjacent cell. The maze has the following properties: - It contains no triangles; that is, there do not exist three distinct cells that are pairwise adjacent. - From any cell, one can reach any other cell. The chase consists of many rounds. In each round, each person makes at most one move. loidc moves first in every round, then cony moves. If loidc and cony occupy the same cell at any time, we may never see loidc again. loidc is very scared. He asks you to tell him whether he will be caught by cony, and in how many rounds cony will catch him (assuming both are sufficiently clever).

The first line contains $4$ integers $n, m, a, b$, separated by single spaces ($2 \leq n \leq 3000$, $n - 1 \leq m \leq 15000$, $1 \leq a, b \leq n$). They denote the number of cells in the maze, the number of adjacent pairs (undirected edges), and the starting positions of loidc and cony, respectively. Each of the following $m$ lines contains two integers separated by a single space, indicating an adjacent pair of cell indices. Between any two adjacent cells, there is exactly one edge.

Output the single word `NO` if cony cannot catch loidc; otherwise output an integer, the minimum number of rounds needed for cony to catch loidc.

Translated by ChatGPT 5