Processing math: 100%
Long leg - MarisaOJ: Marisa Online Judge

Long leg

Time limit: 1000 ms
Memory limit: 256 MB
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