Giải bài trực tuyến

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