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, m ≤ 105), source s and destination d (1 ≤ s, d ≤ n). 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.