e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Shortest even path

Shortest even path

Undirected unweighted graph is given. Find the shortest path between two vertices of even length.

Input

First line contains four integers: number of vertices n, number of edges m (n, m105), source s and destination d (1s, dn). Each of the next m lines contains two integers a and b describing an undirected edge (a, b).

Output

Print the shortest distance from s to d. The length of the path (number of edges in the path) must be even. If there is no path of even length between s and d, print -1.

prb10082.gif

Time limit 1 second
Memory limit 128 MiB
Input example #1
8 8 1 6
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 6
Output example #1
6
Input example #2
6 5 1 6
1 2
2 3
3 4
4 5
5 6
Output example #2
-1
Author Mykhailo Medvediev