Transfer

Time limit2sMemory limit256 MB

Summary

Given hypertubes each connecting K stations totally, find the fewest stations visited traveling from station 1 to station N.

Level: Medium5 of 10
Topics: BFS, Graph, Hash map, Implementation
Solved: No attempts yet

Problem

In the far future, the most widely used form of public transportation is the hypertube. A single hypertube directly connects $K$ stations to one another; that is, you can travel between any two stations on the same hypertube in a single move. Starting from station $1$ and arriving at station $N$ , find the minimum number of stations you visit. (Both the starting station and the destination station count as visited.)

Input

The first line contains the number of stations $N$ , the number of stations that one hypertube connects $K$ , and the number of hypertubes $M$ . ( $1 \le N \le 100000$ , $1 \le K, M \le 1000$ )

Each of the next $M$ lines describes one hypertube. A line contains $K$ integers: the numbers of the stations that this hypertube connects to one another.

Output

Print the minimum number of stations visited on a trip from station $1$ to station $N$ . If station $N$ cannot be reached, print $-1$ .

Examples2

Example 1
Input
```
9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9
```
Expected output
```
4
```

Example 2

Input

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

Expected output