1648 : 초월 공간 (HIPERCIJEVI)
- 제한시간
- 1000 ms
- 메모리제한
- 32 MB
- 해결횟수
- 3 회
- 시도횟수
- 14 회
문제
N개의 점과 M개의 초월 공간이 있다. 각 초월 공간은 K개의 점을 포함하며, 같은 초월 공간 위에 있는 점들 사이에는 자유롭게 왕래가 가능하다.
이 때 1번 점에서 N번 점으로 가기 위해 방문해야 하는(1, N번 점 포함) 최소 점의 수를 구하는 프로그램을 작성하여라.
입력형식
첫 번째 줄에는 N, K, M이 주어진다.
(1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1,000)
두 번째 줄부터 M개의 줄에는 각 초월 공간이 포함하는 K개의 점의 번호(1 이상 N 이하의 자연수)가 주어진다.
출력형식
1번 점에서 N번 점으로 가기 위해 방문해야 하는 최소 점의 수를 출력한다.
만약 1번 점에서 N번 점으로 갈 수 없으면 -1을 출력한다.
입력 예9 3 5 1 2 3 1 4 5 3 6 7 5 6 7 6 8 9 |
출력 예4 |
Hint!
입력 예 2
15 8 4
11 12 8 14 13 6 10 7
1 5 8 12 13 6 2 4
10 15 4 5 9 8 14 12
11 12 14 3 5 6 1 13
출력 예 2
3