Chia Hai Nhóm Tương Khắc

Có $n$ thành viên và $m$ cặp không được xếp chung nhóm. Cần gán mỗi thành viên vào nhóm $1$ hoặc nhóm $2$ sao cho hai thành viên của mọi cặp đã cho luôn thuộc hai nhóm khác nhau. Kích thước hai nhóm không cần bằng nhau.

Hãy in một cách chia hợp lệ, hoặc kết luận rằng không thể thực hiện.

Input

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Mỗi dòng trong $m$ dòng tiếp theo chứa hai số nguyên $u$ và $v$, mô tả một cặp không được cùng nhóm. Không có cặp trùng và $u\ne v$.

Output

• Nếu có cách chia, in $n$ số; số thứ $i$ là $1$ hoặc $2$, biểu thị nhóm của thành viên $i$. Có thể in bất kỳ cách chia hợp lệ nào.

• Nếu không có cách chia, in IMPOSSIBLE.

Constraints

• $1\le n\le 10^5$.
• $1\le m\le 2\cdot 10^5$.
• $1\le u,v\le n,u\ne v$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m\le 30$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

6 4
1 2
2 3
4 5
5 6

1 2 1 1 2 1