A relay network has n towers, numbered 1 to n, and m two-way wires between pairs of towers. A signal originates at a chosen source tower s and spreads outward: from any tower holding the signal, it reaches every directly-wired neighbor one hop later.
If the signal eventually reaches every one of the n towers, report the number of hops needed for the LAST tower to receive it (the maximum shortest-path distance from s to any tower). If at least one tower can never receive the signal, report -1 instead.
Input format
Line 1: two integers n and m — number of towers (1-indexed) and number of wires.
Next m lines: two integers u v — an undirected wire between tower u and tower v.
Last line: one integer s — the source tower.
Output format
A single integer: the maximum hop distance from s to reach every tower, or -1 if some tower is unreachable.
Constraints
- 1 ≤ n ≤ 40
- 0 ≤ m ≤ 200
- 1 ≤ u, v, s ≤ n