Maze Pursuit: Will Cony Catch Loidc?

Loidc has been chased into a maze by Cony. The maze consists of n numbered blocks (from 1 to n). For every pair of distinct blocks, it is known whether they are adjacent. The maze has no triangles; that is, there exist no three distinct blocks such that every two of them are adjacent. In addition, the maze is connected (from any block you can reach any other block).

Loidc and Cony are initially placed on some blocks of the maze. In each round of the pursuit, first Loidc makes a move and then Cony makes hers. In a move a player may either stay in the same block or move to any block adjacent to the one he or she is in. If at any time (either immediately after Loidc’s move or after Cony’s move) the two are on the same block, then Cony catches Loidc and the chase ends – and it is likely that Loidc will never be seen again.

Assuming both play optimally (with Loidc trying to delay capture as long as possible and Cony trying to minimize the number of rounds until capture), determine whether Cony can eventually catch Loidc. If she can, output the number of rounds required for Cony to catch Loidc; otherwise output never.

Note on rounds: A round starts with Loidc’s move and then Cony’s move. If capture occurs during a round (either immediately when Loidc moves into Cony’s current block or when Cony moves onto Loidc’s block) that entire round is counted as 1 round.

The following recurrence describes the game. Let \(F(r,c)\) be the number of rounds remaining when the round starts with Loidc at block \(r\) and Cony at block \(c\). Then

[ F(r,c)=\max_{r'\in N(r)}\Bigg{ ;\begin{cases} 1, & \text{if } r' = c,\ \min_{c'\in N(c)}\Big{ ;!1 ;\text{if } c'=r' ;\text{ else } 1 + F(r',c')\Big}, & \text{if } r'\neq c, \end{cases} \Bigg} ]

Here, for any block \(x\), \(N(x)\) is the set of possible moves from \(x\); since staying in place is allowed, \(x\in N(x)\). If under optimal play Loidc can avoid capture indefinitely, we define \(F(r,c)=\infty\) (and the answer should be output as never).

inputFormat

The first line contains two integers n and m — the number of blocks and the number of edges in the maze.

The second line contains two integers s and t — the initial positions of Loidc and Cony respectively (1-indexed).

Then follow m lines, each containing two integers u and v, indicating that blocks u and v are adjacent. The maze is undirected, connected, and contains no triangles. Note that every block also has a self‐loop (i.e. staying in place is allowed).

outputFormat

If Cony can eventually catch Loidc under optimal play, output the number of rounds required. Otherwise, output never (without quotes).

sample

3 2
1 3
1 2
2 3

2