환승권으로 이어지는 정류장

문제

한 마을의 버스 운영팀이 정류장 사이에서 사용할 수 있는 환승권을 정리하고 있다. 정류장은 1번부터 N번까지 있으며, 환승권에는 출발 정류장과 도착 정류장이 하나씩 적혀 있다. 출발 정류장에서 해당 환승권을 사용하면 적힌 도착 정류장으로 이동한다. 반대 방향으로도 이동할 수 있다는 뜻은 아니며, 반대 방향의 이동에는 별도의 환승권이 필요하다. 여행자는 S번 정류장에서 출발하여 T번 정류장에 도착하려 한다. 현재 정류장을 출발지로 하는 환승권 중 하나를 골라 사용할 수 있다. 환승권 한 장을 사용하면 이동 횟수가 정확히 1 증가한다. 이동에 걸리는 실제 시간이나 두 정류장 사이의 거리는 고려하지 않는다. 어떤 환승권이든 사용할 수 있는 수량은 충분하므로 같은 종류의 환승권을 여러 번 사용해도 된다. 목록에 같은 출발지와 도착지를 가진 환승권이 여러 번 나타날 수 있다. 이러한 항목들은 모두 같은 이동을 허용하며, 중복 항목이 있다고 해서 한 번의 이동에 여러 장을 사용해야 하는 것은 아니다. 출발지와 도착지가 같은 환승권도 주어질 수 있으며, 이를 사용해도 이동 횟수는 1 증가한다. 일부 정류장에는 들어가거나 나갈 수 있는 환승권이 없을 수도 있다. 여행자는 중간에 방문하는 정류장이나 사용하는 환승권의 종류에 제한을 두지 않는다. 같은 정류장을 다시 방문하는 것도 가능하다. 단, 목록에 없는 이동을 하거나 버스를 타지 않고 다른 정류장으로 옮겨 갈 수는 없다. S와 T가 같다면 환승권을 사용하지 않은 상태로 이미 목적지에 도착한 것으로 본다. 정류장과 환승권 목록이 주어질 때 목적지에 도착하는 데 필요한 최소 이동 횟수를 구한다. 최소 횟수를 달성하는 이동 순서가 여러 개여도 그 횟수만 출력한다. 어떤 이동 순서를 선택해도 목적지에 도착할 수 없다면 -1을 출력한다.

입력

첫째 줄에 정수 N, M이 주어진다. 1 ≤ N ≤ 20,000, 0 ≤ M ≤ 30,000이다.
둘째 줄에 정수 S, T가 주어진다. 1 ≤ S, T ≤ N이다.
다음 M개 줄에는 환승권의 출발지 u와 도착지 v가 정수로 주어진다. 1 ≤ u, v ≤ N이다. 중복 항목과 u = v인 항목을 허용한다.

출력

S번 정류장에서 T번 정류장까지의 최소 이동 횟수를 정수 하나로 출력한다. 도착할 수 없다면 -1을 출력한다.

6 7
1 6
1 2
2 3
3 6
1 4
4 6
6 4
2 2

2

4 3
4 1
1 2
2 3
3 4

-1

1 0
1 1

0

출처: Devin.KR 자체 제작