Có n học sinh trong lớp và có m mối quan hệ bạn bè. Nhiệm vụ của bạn là chia học sinh thành hai nhóm sao cho không có hai học sinh nào trong cùng một nhóm là bạn.

Input

Dòng đầu tiên gồm 2 số n và m (~ 2 \le n \le 2.10^5 , 1 \le m \le 2.10^5 ~) - số học sinh và số mối quen hệ bạn bè. Các học sinh được đánh số từ 1 đến n.

M dòng tiếp theo mô tả các mối quan hệ bạn bè. Mỗi dòng chứa hai số nguyên u và v: học sinh u và v là bạn bè.

Output

In một ví dụ về cách xây dựng hai nhóm. Đối với mỗi học sinh, in "1" hoặc "2" tùy thuộc vào nhóm mà học sinh đó sẽ được gán. Có nhiều cách chia nhóm nhưng bạn hãy tìm cách gán học sinh 1 vào nhóm 1.

Nếu không có cách chia nhóm, in "IMPOSSIBLE".

Examples

Input

5 3
1 2
1 3
4 5

Output

1 2 2 1 2