VOI 06 Bài 5 - Mạng máy tính

View as PDF

Submit solution


Points: 0.21 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Ðề thi quốc gia 2006
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.