환승

시간 제한2초메모리 제한256 MB

요약

K개의 역을 완전히 연결하는 하이퍼튜브들이 주어질 때 1번 역에서 N번 역까지 이동하며 방문하는 역 수의 최솟값을 구한다.

난이도: 보통10점 중 5점
유형: BFS, 그래프, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

아주 먼 미래, 사람들이 가장 많이 이용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 $K$ 개의 역을 서로 직접 연결한다. 즉, 같은 하이퍼튜브에 속한 두 역 사이는 한 번의 이동으로 오갈 수 있다. $1$ 번 역에서 출발하여 $N$ 번 역에 도착할 때, 방문하는 역의 최소 개수를 구하여라. (출발역과 도착역도 방문한 역으로 센다.)

입력

첫째 줄에 역의 수 $N$ , 하이퍼튜브 하나가 연결하는 역의 개수 $K$ , 하이퍼튜브의 개수 $M$ 이 주어진다. ( $1 \le N \le 100000$ , $1 \le K, M \le 1000$ )

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

출력

첫째 줄에 $1$ 번 역에서 $N$ 번 역까지 가는 동안 방문하는 역의 최소 개수를 출력한다. 도달할 수 없으면 $-1$ 을 출력한다.

예제2

예제 1
입력
```
9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9
```
예상 출력
```
4
```

예제 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

예상 출력