Shortest even path

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

Esempi