Yozgi maktab 4-contest
Contest Problems
Problem Tasks
# Date State
Not Contest
# Date State

D. 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