문제
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을 출력한다.
예제1
입력
935
123
145
367
567
689
출력
4
예제2
입력
1584
1112814136107
1581213624
101545981412
111214356113
출력
3
출처
COCI 2012/2013 - Contest 5
2013.03.09 모의테스트4
2013.03.09 모의테스트4