BOJ 8052 Agents

문제 링크:

문제 내용

$n$개의 정점과 $m$개의 방향 간선을 갖는 방향 그래프가 주어집니다.

에이전트 1은 $a_1$번 정점에, 에이전트 2는 $a_2$번 정점에 있습니다. 각 에이전트는 하루가 지날 때마다 하나의 간선을 따라 이동할 수 있으며, 연속 이틀 동안 같은 정점에 머물 수 없습니다.

이때, 두 에이전트가 같은 날에 서로 같은 정점을 방문하는 데 걸리는 최소 시간을 구하세요.

입력

첫 번째 줄에는 정점의 수 $n$과 간선의 수 $m$이 주어집니다. ($1 \le n \le 250$, $0 \le m \le n(n-1)$)

두 번째 줄에는 두 에이전트가 현재 있는 정점의 번호 $a_1$과 $a_2$가 주어집니다. ($1 \le a_1, a_2 \le n$, $a_1 \neq a_2$)

다음 $m$줄에 걸쳐서, 각 간선의 출발 정점의 번호 $u$와 도착 정점의 번호 $v$가 주어집니다. ($1 \le u, v \le n$, $u \neq v$)

중복된 간선은 주어지지 않습니다.

출력

두 에이전트가 만나는 것이 가능하다면, 두 에이전트가 만나는 데 걸리는 최소 일수를 출력합니다.

불가능하다면, NIE를 출력합니다.

문제 풀이