추격

추격은 두 명이 즐기는 보드 게임으로, 두 플레이어를 각각 A와 B라고 부른다. 보드는 $1$번부터 $n$번까지 번호가 붙은 칸들로 이루어져 있다. 서로 다른 두 칸에 대해 두 칸이 인접한지 여부가 주어진다. 각 플레이어는 말을 하나씩 가지며, 게임을 시작할 때 두 말은 서로 다른 고정된 칸에 놓인다. 한 번 움직일 때 플레이어는 말을 그 자리에 그대로 두거나, 인접한 칸으로 옮길 수 있다.

보드는 다음 두 성질을 만족한다.

• 삼각형이 없다. 즉, 세 칸이 서로 모두 인접한 경우는 존재하지 않는다.
• 연결되어 있다. 즉, 두 플레이어 모두 모든 칸에 도달할 수 있다.

게임은 여러 턴으로 이루어진다. 각 턴에서 두 플레이어는 각각 한 번씩 움직이며, 항상 A가 먼저 움직인 뒤 B가 움직인다.

두 말이 같은 칸에 놓이는 순간 B가 A를 잡은 것이다. 주어진 시작 위치에서, A가 어떻게 움직이더라도 B가 반드시 A를 잡을 수 있는지 판단하라. 잡을 수 있다면, 두 플레이어가 모두 최적으로 움직일 때(A는 최대한 오래 도망치려 하고, B는 최대한 빨리 잡으려 한다) B가 A를 잡기까지 필요한 최소 턴 수를 구하라.

위 그림의 보드를 보자. 인접한 칸(원으로 표시)은 간선으로 연결되어 있다. A와 B의 말이 각각 $9$번과 $4$번 칸에서 시작하면, 최적으로 움직일 때 B는 세 번째 턴에 A를 잡는다. 반면 $8$번 칸(A)과 $4$번 칸(B)에서 시작하면, A가 올바르게 움직이는 한 B는 결코 A를 잡을 수 없다.

보드의 정보와 두 말의 시작 칸을 입력받아, B가 A를 잡을 수 있는지 판단하고, 잡을 수 있다면 최적으로 움직일 때 필요한 최소 턴 수를 계산하여 출력하는 프로그램을 작성하라.

첫째 줄에 네 정수 $n$, $m$, $a$, $b$가 공백으로 구분되어 주어진다. 이때 $2 \le n \le 3000$, $n-1 \le m \le 15000$, $1 \le a, b \le n$, $a \ne b$이다. 각각 칸의 개수, 인접한 (순서 없는) 칸 쌍의 개수, A의 말이 시작하는 칸 번호, B의 말이 시작하는 칸 번호를 뜻한다.

이어지는 $m$개의 줄에는 각각 서로 다른 두 정수가 공백으로 구분되어 주어지며, 인접한 두 칸의 번호를 나타낸다.

다음 중 하나를 한 줄에 출력한다.

• B가 A를 잡을 수 없으면 문자열 NIE,
• 잡을 수 있으면 최적으로 움직일 때 B가 A를 잡기까지 필요한 최소 턴 수(정수 하나).