Loading...
Loading...
Loading...
Meera works for the town planning office. The town has n junctions, numbered 1 to n, and m two-way roads. Each road joins two different junctions, and no two roads join the same pair.
A round trip starts at a junction, uses at least one road, never uses the same road twice, and comes back to where it started. Going along a road and straight back on the same road does not count.
Print YES if the road network has a round trip anywhere, otherwise print NO.
YES or NO.Example 1
Input
4 3 1 2 2 3 3 4
Output
NO
A straight line of roads. Every trip has to come back the way it went.
Example 2
Input
5 4 1 2 2 3 3 1 4 5
Output
YES
The roads 1 → 2 → 3 → 1 form a round trip.
Try the problem first. Open one hint at a time.
Walk the roads from a junction and remember, for every junction you reach, the junction you came from. Call it the parent.
When you look at a road from the current junction to a junction that is already visited, it is either the road back to the parent or a road that closes a loop.
Only the road back to the parent is harmless. Any other visited neighbour means a round trip exists.
The town may be in several separate parts. Start a new walk from every junction that is not visited yet.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor