COCI 2012/2013 - Contest 5<br>2013.03.09 모의테스트4- 초월 공간 (HIPERCIJEVI) > 문제은행 : 정보올림피아드&알고리즘




1648 : 초월 공간 (HIPERCIJEVI)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
12 회   
시도횟수
89 회   

문제

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




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP