Cities are joined by two-way roads. Find the minimum number of roads on a route from s to t.

Input

The first line contains n, m, s, and t. The next m lines contain two-way roads.

• 1 <= s, t <= n <= 1000
• 0 <= m < 2000

Output

Print the shortest distance in edges, or -1 if t is unreachable.

Example

Input

5 5 1 4
1 2
2 3
3 5
5 4
2 4

Output

2