A social network has n members numbered 1 through n. Some pairs of members are mutual friends. The degrees of separation between two members is the minimum number of friendship links you must cross to travel from one to the other.
Given a start member s and a target member t, report their degrees of separation. If s equals t the answer is 0. If there is no chain of friendships connecting them, report -1.
Input format
Line 1: two integers n and m.
Next m lines: two integers u and v, a mutual friendship between members u and v.
Last line: two integers s and t.
Output format
A single integer: the degrees of separation, or -1 if t is unreachable from s.
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 1 <= u, v, s, t <= n