A Cycle Problem

View as PDF
Submit solution
Points: 5
Time limit: 0.5s
Memory limit: 64M
Author:
Ninjaclasher
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.

Subtasks

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

YES

Sample Input 2

4 3
1 2
2 3
2 4

Sample Output 2

NO

Comments