365. Does the Graph Have a Cycle

Core1000 ms256 MBSolved by 0%

Print Yes if the undirected graph contains a cycle, and No otherwise.

Walk the graph and watch for an edge that leads to a vertex already visited. That vertex closes a loop, so a cycle exists.

There is one thing to be careful about, and it is the whole problem. Every undirected edge appears in both adjacency lists, so from vertex 2 you will always see the edge back to the vertex you just came from. That is not a cycle. Carry the vertex you arrived from and skip it.

The graph may be disconnected, so start a traversal from every unvisited vertex, exactly as in problem 363.

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.

Input

The first line contains two integers n and m, the number of vertices and edges. Each of the next m lines contains two integers u and v, an undirected edge between those vertices. Vertices are numbered 1 to n.

Output

Print Yes or No on one line.

Input3 3 1 2 2 3 3 1

OutputYes

Noteis a triangle, the smallest cycle

Input4 3 1 2 2 3 3 4

OutputNo

Noteis a path, where the parent check is what stops a false positive

Input5 4 1 2 2 3 3 1 4 5

OutputYes

Notehas the cycle in the first component and an acyclic second one

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution