요원들

바이트랜드 중앙정보국은 최근 현장 요원들이 여러 차례 실수를 저지르자 요원들의 활동 방식을 개선하기로 했다. 지금까지 가장 큰 골칫거리는 요원들이 안전하게 만나도록 주선하는 일이었고, 이 문제를 푸는 것이 여러분의 임무다.

바이트랜드의 도로망과 두 요원의 시작 도시가 주어질 때, 안전한 만남을 주선할 수 있는지, 가능하다면 며칠이 걸리는지 판단하라.

만남이 안전하다고 인정받으려면 두 요원은 다음 규칙을 모두 지켜야 한다.

• 요원은 낮 동안 이동하고 저녁에 만난다.
• 요원은 매일 반드시 다른 도시로 이동해야 하며, 같은 도시에 머무를 수 없다.
• 요원은 도시를 잇는 도로를 통해서만 이동할 수 있고, 바이트랜드의 모든 도로는 일방통행이다.
• 의심을 사지 않기 위해 요원은 하루에 너무 멀리 이동할 수 없다. 하루 동안에는 바로 인접한 도시까지만 갈 수 있다.
• 인접한 두 도시는 충분히 가까워서, 아침에 한 도시를 떠난 요원은 저녁이 되기 전에 반드시 다음 도시에 도착한다.
• 두 요원이 같은 저녁에 같은 도시에 있으면 만남이 이루어진 것으로 본다.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 도시의 수, 도로망, 두 요원의 시작 도시를 읽는다.
• 안전한 만남이 가능한지, 가능하다면 주선하는 데 필요한 최소 일수를 구한다.
• 그 결과를 표준 출력에 쓴다.

첫째 줄에 도시의 수 $n$과 도로의 수 $m$이 공백 하나로 구분되어 주어진다. $1 \le n \le 250$, $0 \le m \le n \cdot (n-1)$이다. 도시는 $1$번부터 $n$번까지 번호가 매겨져 있다.

둘째 줄에 요원 1과 요원 2의 시작 도시를 나타내는 두 정수 $a_1$과 $a_2$가 공백 하나로 구분되어 주어진다. $1 \le a_1, a_2 \le n$이고 $a_1 \ne a_2$이다.

다음 $m$개의 줄에는 각각 두 정수 $a$와 $b$가 공백 하나로 구분되어 주어지며, $1 \le a, b \le n$, $a \ne b$이다. 이는 도시 $a$에서 도시 $b$로 가는 일방통행 도로가 있음을 뜻한다.

다음 내용을 한 줄에 출력한다.

• 안전한 만남이 가능하다면, 만남을 주선하는 데 필요한 최소 일수를 나타내는 양의 정수 하나를 출력한다.
• 안전한 만남이 불가능하다면 NIE(폴란드어로 "아니오")를 출력한다.