Du lịch

View as PDF
Submit solution
Points: 0.66 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Dựa theo BOI 2001
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một công ty du lịch tổ chức cho 1 đoàn du khách nước ngoài đi du lịch M thành phố ở Việt Nam . Tuy nhiên mỗi du khách lại có 2 yêu cầu . Mỗi yêu cầu có dạng "Không muốn đi thành phố A" hoặc "Muốn đi thành phố A" (A là chỉ số thành phố mà người đó yêu cầu). Có thể có trường hợp 2 yêu cầu của khách là "Muốn đi thành phố A" và "Không muốn đi thành phố A". Vì các du khách này là người nước ngoài nên rất khó tính, họ muốn ít nhất 1 trong 2 yêu cầu của họ phải được đáp ứng. Bên công ty du lịch đã đau đầu tìm cách chọn ra các thành phố để đưa đoàn du khách đi mà vẫn chưa tìm được cách nào cả. Bạn được yêu cầu giúp công ty du lịch này chọn ra 1 số thành phố để đưa đoàn du khách này đi mà lại vừa thoả mãn được các du khách này .

Input

Dòng đầu tiên gồm ~2~ số nguyên ~N~ và ~M~ ~(1 \le N \le 20000, 1 \le M \le 8000)~ tương ứng là số khách du lịch và số thành phố.

~N~ dòng tiếp theo gồm ~2~ số nguyên ~u, v~, ~-M \le u, v \le M~ ~(u \ne 0, v \ne 0)~ mô tả yêu cầu của khách thứ ~i~ (số dương nếu yêu cầu du khách ~i~ muốn đi thành phố đó và số âm nếu không muốn đi thành phố đó).

Output

Dòng 1: Ghi YES nếu có phương án thoả mãn yêu cầu các du khách và ghi NO trong trường hợp ngược lại.

Nếu YES thì ghi tiếp theo như sau:

Dòng 2 : số nguyên ~K~ là số thành phố được chọn.

Dòng 3 : Gồm ~K~ số nguyên là chỉ số của các thành phố được chọn.

Sample Input

2 3
-1 -2
1 2

Sample Output

YES
2
1 3

Comments

Please read the guidelines before commenting.