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
• Đồ thị đơn: không có cạnh khuyên (u != v) và không có hai cạnh trùng nhau.

Chấm điểm

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.