Mạng chẵn lẻ

View as PDF

Submit solution

Points: 0.89 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

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.

Input

  • Dòng đầu tiên chứa số ~N~ ~(N \le 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~.

Output

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

Sample Input 1

5
1 2
2 3
3 4
4 5
5 1

Sample Output 1

YES

Sample Input 2

3 
1 2

Sample Output 2

NO
2
1 3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.