Fewest links between two offices

Problem

Offices are joined by two-way links. Print the smallest number of links on any route from office s to office t, or -1 if no route exists.

Input: Line 1: n and m, the number of nodes and edges. Then m lines, each with two node numbers a and b for a two-way link. Nodes are numbered 0 to n - 1. The last line has s and t.
Output: One integer: the fewest links, or -1.
Constraints: 1 ≤ n ≤ 100000
0 ≤ m ≤ 200000
No node is linked to itself and no pair is listed twice
0 ≤ s, t < n

Example 1

Input

Output

Both routes use three links.

Example 2

Input

Output

-1

Try the problem first. Open one hint at a time.

Hint 1

Every link counts the same, so use BFS.

Hint 2

Store a distance for each node when you first reach it.

Write your Python code, run it on the examples and submit it to hidden tests.