Fewest Hops

Medium#graphs #bfs· solved by 0 · time limit 2.0 s

A network of $n$ routers is connected by $m$ cables (undirected). What is the minimum number of cables a packet must cross to go from router $s$ to router $t$ ? Print -1 if it can't reach.

Input

$n$ and $m$ , $m$ lines u v, then s t.

Output

The minimum number of hops, or -1.

Constraints

$1 \le n \le 10^5$ , $0 \le m \le 2 \times 10^5$

Sample 1

Input

Output

Sample 2

Input

3 1
1 2
1 3

Output

-1