Detect Cycle in Undirected Graph

Problem statement

A neighborhood network connects stations with undirected links. An inspector needs to know whether the network contains a closed route that returns to its starting station without reusing an edge or intermediate station. Your task Determine whether the undirected graph contains a cycle. Important details The immediate edge back to a traversal parent is not evidence of a cycle, since each undirected edge is seen from both endpoints. Inspect every component, including components not connected to vertex zero. Isolated vertices do not form cycles. Worked example Links 0-1, 1-2 and 2-0 form a triangle, so the answer is true. Removing the last link leaves a path and changes the answer to false.

Input format

First line: n m. Next m lines: endpoints u v of undirected edges. Vertices are numbered 0 through n-1.

Output format

Print true if the condition holds, otherwise false.

Constraints

1 <= n <= 2000; 0 <= m <= 10000; endpoints are valid, with no self-loops or repeated edges.

Sample input

3 3
0 1
1 2
2 0

Sample output

true