A transit map has n stations connected by two-way corridors. Every corridor takes exactly one hop to traverse. Given a start station and a destination station, determine the minimum number of hops needed to travel from start to destination.
If the destination cannot be reached from the start, report -1. If the start and destination are the same station, the answer is 0.
Input format
Line 1: two integers n and m — the number of stations and the number of corridors.
Next m lines: two integers u v (0-indexed) meaning there is a two-way corridor between station u and station v.
Last line: two integers s t — the start station and the destination station.
Output format
A single integer: the minimum number of hops from s to t, or -1 if t is unreachable from s.
Constraints
- 1 \u2264 n \u2264 100000
- 0 \u2264 m \u2264 200000
- 0 \u2264 u, v, s, t < n
- There are no self-loops. There may be at most one corridor between any pair of stations.