Fewest Hops

Difficulty: 1300 4000 ms 128 MB

bfs graphs

Print the minimum number of links on a route from S to T, or −1 if unreachable.

Input: the first line has N and M; each of the next M lines has an edge u v (1-based). The last line has S and T.

Output: the shortest hop count, or −1.

Constraints:

• 1 ≤ N ≤ 10⁴
• 0 ≤ M ≤ 2×10⁴
• multiple edges and self-loops may appear

Sample Tests

5 4
1 2
2 3
3 4
1 4
1 4

1

3 1
1 2
1 3

-1

Read the Editorial