A metro network has n stations numbered 1 through n. Some pairs of stations are joined by a bidirectional track. A rider standing at a start station s wants to reach a target station t, transferring freely between any tracks that meet at a station.
Decide whether the rider can reach t from s. Note that a station is always considered reachable from itself.
Line 1: two integers n and m.
Next m lines: two integers u and v, a bidirectional track between stations u and v.
Last line: two integers s and t, the start and target stations.
Print REACHABLE if the rider can reach t from s, otherwise print UNREACHABLE.
Example 1
Input
5 3 1 2 2 3 4 5 1 3
Expected
REACHABLE
Explanation
From station 1 you can walk 1-2-3, so station 3 is REACHABLE.
Example 2
Input
5 3 1 2 2 3 4 5 1 5
Expected
UNREACHABLE
Explanation
Station 1 is in the group {1,2,3}, while station 5 is in {4,5}; no track connects the groups, so it is UNREACHABLE.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →