Detect Cycle in an Undirected Graph (DFS)

Detect Cycle in an Undirected Graph (DFS)

Determine whether an undirected graph contains a cycle using DFS.

Input format

The first line contains N and M. The next M lines contain edge pairs (undirected).

Output format

Print true if the graph contains a cycle (using DFS), false otherwise.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

4 6
0 2
2 3
1 2
1 3
0 1
0 3

true

10 20
4 8
1 8
1 7
1 6
0 7
0 4
6 9
3 7
3 8
6 8
4 7
5 6
2 5
1 5
0 2
7 8
8 9
5 9
6 7
0 6

true