#2026 · Trại Hè Bất Ổn Của Lớp Trưởng Chí Thành!

Lớp trưởng Chí Thành đang đau đầu nhức óc vì phải tổ chức chia đội cho n bạn sinh viên trong khoa Công Nghệ Thông Tin đi dã ngoại. Khổ một nỗi, trong lớp có m cặp "oan gia ngõ hẹp" cứ hễ gặp nhau là cãi lộn tung chảo (đứa thì thích code C++, đứa lại một mực bênh vực Java).

Thành bắt buộc phải chia cả lớp thành đúng 2 nhóm sao cho không có bất kỳ cặp oan gia nào bị xếp chung vào cùng một nhóm để bảo toàn tính mạng cho cả lớp.

Cậu hãy trổ tài làm quân sư thuật toán, giúp Chí Thành tìm ra một cách chia nhóm hòa bình nhé!

• Dòng đầu tiên là 2 số nguyên n và m (1 \leq n \leq 100.000, 1 \leq m \leq 200.000) thể hiện số lượng sinh viên và số lượng cặp oan gia.

• m dòng tiếp theo, mỗi dòng là một cặp số nguyên u và v cho biết sinh viên u và sinh viên v cứ gặp nhau là "tới công chuyện". (1 \leq u ≠ v \leq n).

In ra n số nguyên, số thứ i (là 1 hoặc 2) đại diện cho nhóm mà bạn sinh viên thứ i được phân vào.

Nếu bè phái phức tạp đến mức Chí Thành cũng phải bó tay, hãy in ra phũ phàng: IMPOSSIBLE.