Shortest even path

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

Input

The first line contains four integers: number of vertices $n$, number of edges $m(n,m\le 10^5)$, source $s$ and destination $d(1\le s,d\le 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$.

Examples