문제

N개의 정점과 M개의 연결 통로가 있다.

각 통로는 정확히 K개의 정점을 연결하며, 같은 통로에 포함된 정점들 사이에서는 한 번의 통로 이용으로 이동할 수 있다.

1번 정점에서 N번 정점에 도달할 때 방문하는 정점 수의 최솟값을 출력하라.

도달 불가능하면 -1을 출력한다.

입력 설명

첫째 줄에 정점의 수 N, 한 연결 통로가 포함하는 정점의 개수 K, 연결 통로의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 연결 통로의 정보가 한 줄에 하나씩 주어진다.

각 줄에는 그 통로가 포함하는 K개의 정점 번호가 주어진다.

출력 설명

첫째 줄에 1번 정점에서 N번 정점으로 가는 동안 방문하는 정점 개수의 최솟값을 출력한다.

도달할 수 없다면 -1을 출력한다.

예제 입력 1

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

예제 출력 1

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

예제 출력 2

3