Any Cycle at All

Difficulty: 1400 4000 ms 128 MB

graphs union-find

Does the undirected graph contain any cycle (self-loops and multi-edges count)?

Input: the first line has N and M; each of the next M lines has an edge u v (1-based).

Output: YES or NO.

Constraints:

• 1 ≤ N ≤ 10⁴
• 0 ≤ M ≤ 2×10⁴
• multiple edges and self-loops may appear

Sample Tests

3 3
1 2
2 3
3 1

YES

3 2
1 2
2 3

NO

Read the Editorial