A Cycle Problem

View as PDF

Submit solution

Points: 5
Time limit: 0.5s
Memory limit: 64M

Problem type

You are given a bidirectional graph. Please check whether this graph contains any cycles. A cycle is defined as a path where the starting and ending nodes are the same, contains at least one edge, and all nodes on the path are unique (except the starting and ending nodes).

Input Specification

The first line will contain two integer, \(N, M\ (1 \le N \le 5 \times 10^6, N-1 \le M \le 5 \times 10^6)\).

The next \(M\) lines will each contain two integers, \(a, b\ (1 \le a, b \le N, a \neq b)\). It is guaranteed the graph is completely connected. However, there may be multiple edges between any \(2\) distinct nodes.

Output Specification

Print YES if there is a cycle, and NO otherwise.


Subtask 1 [50%]

\(N, M \le 1\ 000\)

Subtask 2 [50%]

No further constraints.

Sample Input 1

4 4
1 2
2 1
2 3
3 4

Sample Output 1


Sample Input 2

4 3
1 2
2 3
2 4

Sample Output 2