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

ELECT - Thống nhất đất nước

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


Sau nhiều năm chiến tranh liên miên giữa các Đảng phái , nước X rơi vào tình trạng đói nghèo , người dân khổ cực trăm bề . Nhận thức được tiếp tục kéo dài chiến tranh sẽ càng bất lợi cho đất nước , các Đảng trong nước X đã quyết định họp bàn nhau lại , bỏ qua hiềm khích chung để xây dựng lại đất nước. Việc làm đầu tiên sẽ là họp để chọn ra các vị đại biểu để lập nên Quốc Hội . Mỗi Đảng đã chọn ra 2 gương mặt tiêu biểu nhất cho Đảng của mình để ứng cử vào Quốc Hội . Tuy nhiên trong số các vị đại biểu của các Đảng này thì có một số vị vì lý do cá nhân trong chiến tranh nên rất căm thù nhau ( ví dụ như là ông A của Đảng P ghét ông B của Đảng Q … ) . Vì lý do chính trị mà trong Quốc Hội mỗi Đảng chỉ được phép có một người mà thôi . Ngoài ra để đảm bảo Quốc Hội làm việc 1 cách công minh thì các vị đại biểu Quốc Hội phải được chọn ra sao cho đảm bảo không có ai thù ghét ai cả nếu không rất có thể chiến tranh sẽ lại nổ ra . Bạn là một người yêu chuộng hoà bình đồng thời là 1 lập trình viên siêu hạng . Bạn hãy xem xét xem liệu có 1 cách tổ chức Quốc Hội sao cho thoả mãn được các yêu cầu đề ra hay không ?

Input

Dòng 1 : 2 số nguyên N và M ( 1 ≤ N≤ 8000 , 1 ≤ M ≤ 20000 ) tương ứng là số Đảng và só mối quan hệ thù ghét nhau giữa các thành viên của các Đảng . ( Các thành viên của Đảng 1 có số hiệu là 1 , 2 ; các thành viên của Đảng 2 có số hiệu là 3 , 4 … Thành viên của Đảng i sẽ có số hiệu là i*2-1 và i*2 ) .
M dòng tiếp theo mỗi dòng gồm 2 số nguyên u , v cho biết người u và người v ghét nhau . ( 1 ≤ u < v ≤ N*2 ) .

Output

Dòng 1 : Ghi 0 nếu không có phương án thoả mãn và 1 nếu có phương án thoả mãn.
Nếu dòng 1 là 1 thì dòng thứ 2 ghi ra N số nguyên là số hiệu của các thành viên được chọn vào Quốc Hội .

Example

Input:
3 2
1 3
2 4

Output:
1
1 4 5


Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-03-02
Thời gian chạy:0.100s
Giới hạn mã nguồn:20000B
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 VB.NET
Nguồn bài:Base on problem of Wojciech Rytter

hide comments
2022-10-09 03:29:45
xin cảm ơn bạn
2019-12-19 12:12:25
Bài này khá hay, gợi ý cho các bạn :
(i v i+1) và (!i v !i+1)
(!u v !v)
2015-10-30 11:53:04
Twosat
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.