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≤n,m≤105.
- 1≤k≤10.
- 1≤u,v≤n.
### Example
Input:
332122313
Output:
1