Chase

Chase is a two-player board game; call the players A and B. The board consists of squares numbered from $1$ to $n$. For every pair of distinct squares it is known whether they are adjacent. Each player controls one piece, and at the start of the game the two pieces are placed on fixed, distinct squares. On a move a player may leave the piece where it is or slide it to an adjacent square.

The board has two properties:

• it contains no triangle: there are no three distinct squares that are pairwise adjacent;
• it is connected: every square is reachable by both players.

A game is a sequence of turns. In each turn both players move once, and player A always moves first (A moves, then B moves).

Player B catches player A when both pieces occupy the same square. For the given starting positions, decide whether player B can force a catch no matter how player A plays. If so, find the minimum number of turns player B needs, assuming both play optimally: player A stays free as long as possible, and player B catches as quickly as possible.

Consider the board in the figure. Adjacent squares (drawn as circles) are joined by edges. If the pieces of players A and B start on squares $9$ and $4$, then under optimal play B catches A on the third turn. If instead they start on squares $8$ (player A) and $4$ (player B), then B can never catch A when A plays correctly.

Write a program that reads a board description together with the starting squares of the two pieces, decides whether player B can catch player A, and if so computes the minimum number of turns needed under optimal play, then writes the answer to standard output.

The first line contains four integers $n$, $m$, $a$ and $b$ separated by single spaces, where $2 \le n \le 3000$, $n-1 \le m \le 15000$, $1 \le a, b \le n$ and $a \ne b$. They are, respectively: the number of squares, the number of adjacent (unordered) pairs, the square where player A's piece starts, and the square where player B's piece starts.

Each of the next $m$ lines contains two distinct integers separated by a single space, giving the numbers of two adjacent squares.

Print a single line containing either:

• the word NIE if player B cannot catch player A, or
• one integer: the minimum number of turns player B needs to catch player A under optimal play.