TWOSAT - Du lịch
Giới hạn- Thời gian: 0.066s
- Bộ nhớ: 1536MB
- Mã nguồn: 30000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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à 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 1 : 2 số nguyên N và M ( 1 ≤ N ≤ 20000 , 1 ≤ M ≤ 8000 ) tương ứng là số khách du lịch và số thành phố .
M dòng tiếp theo gồm 2 số nguyên u , v , -M ≤ u ,v ≤ M ( u <> 0 , v <> 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 dương 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 .
Example
Input: 2 3 -1 -2 1 2 Output: YES 2 2 3
- Người up: hard7771988
- Nguồn bài: Dựa theo BOI 2001