Một hệ thống ~n~ máy tính (các máy tính được đánh số từ ~1~ đến ~n)~ được nối lại thành một mạng bởi ~m~ kênh nối, mỗi kênh nối hai máy nào đó và cho phép ta truyền tin một chiều từ máy này đến máy kia. Giả sử ~s~ và ~t~ là ~2~ máy tính trong mạng. Ta gọi đường truyền từ máy ~s~ đến máy ~t~ là một dãy các máy tính và các kênh nối chúng có dạng:
~s = u_{1}~, ~e_{1}~, ~u_{2}~, ..., ~u_{i}~, ~e_{i}~, ~u_{i + 1}~, ..., ~u_{k - 1}~, ~e_{k - 1}~, ~u_{k} = t~
trong đó ~u_{1}~, ~u_{2}~, ..., ~u_{k}~ là các máy tính trong mạng, ~e_{i} -~ kênh truyền tin từ máy ~u_{i}~ đến máy ~u_{i + 1}~. ~(i = 1~, ~2~, ..., ~k - 1)~.
Mạng máy tính được gọi là thông suốt nếu như đối với hai máy ~u~, ~v~ bất kỳ ta luôn có đường truyền tin từ ~u~ đến ~v~ và đường truyền tin từ ~v~ đến ~u~. Mạng máy tính được gọi là hầu như thông suốt nếu đối với hai máy ~u~, ~v~ bất kỳ, hoặc là có đường truyền từ ~u~ đến ~v~, hoặc là có đường truyền từ ~v~ đến ~u~.
Biết rằng mạng máy tính đã cho là hầu như thông suốt nhưng không thông suốt.
Yêu cầu: hãy xác định xem có thể bổ sung đúng một kênh truyền tin để biến mạng đã cho trở thành thông suốt được không?
Input
- Dòng đầu tiên ghi ~2~ số nguyên ~n~ và ~m~.
- Dòng thứ ~i~ trong số ~m~ dòng tiếp theo mô tả kênh nối thứ ~i~ bao gồm ~2~ số nguyên dương ~u_{i}~ và ~v_{i}~ cho biết kênh nối thứ ~i~ cho phép truyền tin từ máy ~u_{i}~ đến máy ~v_{i}~, ~i = 1~, ~2~, ..., ~m~.
Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.
Output
- Dòng đầu tiên ghi 'YES' nếu câu trả lời là khẳng định, ghi 'NO' nếu câu trả lời là phủ định.
- Nếu câu trả lời là khẳng định thì dòng thứ hai ghi hai số nguyên dương ~u~, ~v~ cách nhau bởi dấu cách cho biết cần bổ sung kênh truyền tin từ máy ~u~ đến máy ~v~ để biến mạng thành thông suốt.
Giới hạn
Trong tất cả các test, ~n \leq 2000~, ~m \leq 30000~.
Sample Input
3 2
1 2
2 3
Sample Output
YES
3 1
Bình luận
Bài này greedy được đó
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.