시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 533 118 86 23.691%

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 

출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최소값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

예제 입력

9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

예제 출력

4

힌트

1-3-6-9나 1-5-6-9로 이동하면 된다.

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #5 4번