Xây dựng đội nhóm

Trong một buổi sinh hoạt đội nhóm, FullHouse Dev đang gặp khó khăn trong việc chia nhóm cho các thành viên. Với mối quan hệ bạn bè phức tạp giữa các thành viên, họ cần tìm cách chia thành hai đội sao cho không có hai người bạn nào trong cùng một đội.

Bài toán

FullHouse Dev có \(n\) thành viên và \(m\) mối quan hệ bạn bè giữa họ. Nhiệm vụ là chia các thành viên thành hai đội sao cho không có hai người bạn nào trong cùng một đội. Kích thước của mỗi đội có thể tự do lựa chọn.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng thành viên và số lượng mối quan hệ bạn bè. Các thành viên được đánh số từ \(1,2,\dots,n\).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\): thể hiện thành viên \(a\) và \(b\) là bạn bè của nhau.

OUTPUT FORMAT:

• In ra một chuỗi số, mỗi số là "1" hoặc "2" thể hiện việc phân chia đội cho từng thành viên.
• Nếu không thể chia đội thỏa mãn điều kiện, in ra "IMPOSSIBLE".

Ràng buộc:

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)

Ví dụ

INPUT

5 3
1 2
1 3
4 5

OUTPUT

1 2 2 1 2

Giải thích

Trong ví dụ này:

• Thành viên 1 được xếp vào đội 1
• Thành viên 2 và 3 (là bạn của thành viên 1) được xếp vào đội 2
• Thành viên 4 được xếp vào đội 1
• Thành viên 5 (là bạn của thành viên 4) được xếp vào đội 2

Cách chia này đảm bảo không có hai người bạn nào trong cùng một đội.