Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKONEARC - Mạng máy tính

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkonearc


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 = u1, e1, u2, ..., ui, ei, ui+1, ..., uk-1, ek-1, uk = t

trong đó u1, u2, ..., uk là các máy tính trong mạng, ei - kênh truyền tin từ máy ui đến máy ui+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?

Dữ liệu

  • 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 ui và vi cho biết kênh nối thứ i cho phép truyền tin từ máy ui đến máy vi, 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.

Kết qủa

  • 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.

Hạn chế

Trong tất cả các test, n ≤ 2000, m ≤ 30000.

Ví dụ

Dữ liệu:
3 2
1 2
2 3

Kết qủa
YES
3 1

Được gửi lên bởi:Jimmy
Ngày:2007-12-22
Thời gian chạy:0.100s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED
Nguồn bài:Đề thi quốc gia 2006

hide comments
2015-05-28 12:31:57 nguyenngocanh
write no dc 40 cơ mà
2015-03-10 09:30:38 lucky++
Hơi rối rắm, cũng được.
2014-12-24 05:23:27 Lollipop
bài hay mà bị lỗi hệ thống là sao ??
2014-09-15 14:46:08 Dương Bảo


Last edit: 2014-09-20 11:42:21
2014-08-06 01:36:46 ■■‡[ND] Bee Sociu■■‡
Sao mak duoc 80 thoi nhi ! Trong khi do Write('NO') khong an duoc diem nao ???
2013-12-19 02:31:24 truong cong tra
n
2013-11-28 01:36:42 anh chỉ yêu mình em.....VTNN......
duyet trau cung ac
2013-11-28 01:36:41 anh chỉ yêu mình em.....VTNN......
duyet trau cung ac
2013-11-07 18:01:11 Human Immunodeficiency Virus
ứng dụng tìm kiếm thành phần liên thông mạnh. tìm bậc ra bậc vào của mỗi thành phần liên thông
2012-02-13 05:49:40 anh chỉ yêu mình em....NTMH....
thử dùng sắp xếp topo đưa đến 1 kq rất hài hước :))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.