For an undirected, unweighted graph with $n$ vertices and $m$ edges, you need to find the shortest path from vertex $1$ to vertex $n$ such that at each step, you are allowed to traverse exactly $k$ edges, no more and no less. What is the minimum distance from vertex $1$ to vertex $n$?
### Input
- The first line contains three integers $n$, $m$, and $k$.
- The next $m$ lines each contain two integers $u$ and $v$, representing an edge between vertices $u$ and $v$.
### Output
- Print the length of the shortest path from vertex $1$ to vertex $n$. Print `-1` if no path exists.
### Constraints
- $1 \le n,m \le 10^5$.
- $1 \le k \le 10$.
- $1 \le u, v \le n$.
### Example
Input:
```
3 3 2
1 2
2 3
1 3
```
Output:
```
1
```
