Chu trình kiểm tra đường ống

Bối cảnh và bài toán

Mạng đường ống được mô hình hóa bằng đồ thị vô hướng. Một chu trình nghĩa là tồn tại một tuyến khép kín đi qua ít nhất ba nút khác nhau rồi quay về điểm xuất phát.

Yêu cầu

Xác định mạng có chứa ít nhất một chu trình hay không.

Input

Dòng đầu n, m; tiếp theo m cạnh u, v.

Output

In "YES" nếu có chu trình, ngược lại in "NO".

Ràng buộc

• 1 <= n <= 2*10^5
• 0 <= m <= 2*10^5 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

4 4
1 2
2 3
3 1
3 4

Output

YES

Giải thích. Kết quả phụ thuộc việc DFS gặp một cạnh nối tới đỉnh đã thăm khác cha hiện tại hay không.

Ví dụ 2

Input

4 3
1 2
2 3
3 4

Output

NO

Giải thích. Kết quả phụ thuộc việc DFS gặp một cạnh nối tới đỉnh đã thăm khác cha hiện tại hay không.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Round Trip. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.