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

NKPARITY - Mạng chẵn lẻ

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/nkparity


Có N máy tính đánh số từ 1 đến N được nối với nhau thành một mạng bởi các đoạn nối trực tiếp giữa một số cặp máy nào đó (gọi là kênh). Mạng được gọi là chẵn lẻ nếu như trong nó tìm được hai máy có thể trao đổi thông tin với nhau thông qua một số chẵn kênh cũng như thông qua một số lẻ kênh.

Yêu cầu: Kiểm tra xem mạng đã cho có phải chẵn lẻ hay không? Nếu câu trả lời là phủ định hãy tìm tập con X các máy có lực lượng lớn nhất thoả mãn điều kiện: đối với hai máy bất kỳ trong X nếu chúng có thể trao đổi thông tin với nhau thì bao giờ cũng phải thông qua một số chẵn kênh.

Dữ liệu

  • Dòng đầu tiên chứa số N (N<=300).
  • Mỗi dòng trong số các dòng tiếp theo chứa một cặp số i, j cho biết máy i được nối trực tiếp với máy j.

Kết quả

  • Nếu mạng là chẵn lẻ thì ghi vào dòng đầu tiên thông báo 'YES', ngược lại ghi 'NO' sau đó ghi kết quả theo qui cách sau:
    • Dòng thứ hai ghi số phần tử của tập X.
    • Trong các dòng tiếp theo ghi các chỉ số của các máy trong tập X theo thứ tự tăng dần, các chỉ số được ghi cách nhau bởi ít nhất một dấu cách.

Ví dụ

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

Kết qủa
YES

Dữ liệu
3 
1 2

Kết quả
NO
2
2 3

Được gửi lên bởi:Jimmy
Ngày:2008-01-14
Thời gian chạy: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

hide comments
2014-04-27 14:50:24 John and the cows
ghi YES dc 40 điểm :v

Last edit: 2014-04-28 03:20:50
2014-04-23 11:20:24 an IM3 Ex-Member of Bit
Để ý 1 vài test sau:
5
1 2
1 3
1 4
1 5

5
1 2
2 3
2 4
4 5
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.