Category
Similar Problems
0748. The shortest path
Time limit : 1000 ms
Memory limit : 64 mb
Undiriented graph is given. Find the shortest path from vertex a to vertex b.
Input
The first line contains two integers n and m (1 <= n <= 100000, 0 <= m <= 100000) - the number of vertices and edges. The second line contains two integers a and b - the starting and ending point correspondingly. The next m lines describe the edges.
Output
If the path between a and b does not exist, print -1. Otherwise print in the first line the length l of the shortest path between these two vertices in number of edges.
Tayyorladi: Azat Yusupov
Text from: e-olimp.com
Input |
---|
4 5 1 4 1 3 3 2 2 4 2 1 2 3 |
Output |
2 |
Input |
---|
4 4 2 3 2 1 2 4 4 3 1 3 |
Output |
2 |