Cycle in an Undirected Graph

Return True if the undirected graph with n nodes and the given edges contains a cycle (a path that returns to its start without reusing an edge). Two copies of the same edge [a, b] and [b, a] count as a cycle of length 2, and an edge [a, a] from a node to itself is a cycle.

For n = 4 and edges = [[0, 1], [1, 2], [2, 0], [3, 3]] the answer is True.

Examples

Example 1

Input:

has_cycle_undirected(4, [[0, 1], [1, 2], [2, 0], [3, 3]])

Output:

True

Example 2

Input:

has_cycle_undirected(4, [[0, 1], [1, 2], [2, 3]])

Output:

False

Constraints

• 0 <= n <= 100000
• 0 <= len(edges) <= 200000