Có \(n\) học sinh trong lớp của Uolevi, và \(m\) tình bạn giữa họ. Nhiệm vụ của bạn là chia học sinh thành hai đội theo cách mà không có hai học sinh nào trong một đội là bạn bè. Bạn có thể thoải mái lựa chọn kích thước của các đội.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng học sinh và tình bạn. Các học sinh được đánh số \(1,2,\ldots,n\).
• Sau đó, có \(m\) dòng mô tả các tình bạn. Mỗi dòng có hai số nguyên \(a\) và \(b\): học sinh \(a\) và \(b\) là bạn bè.
• Mỗi tình bạn là giữa hai học sinh khác nhau. Bạn có thể giả định rằng có nhiều nhất một tình bạn giữa bất kỳ hai học sinh nào.

Output

• In một ví dụ về cách xây dựng các nhóm. Đối với mỗi học sinh, in \(1\) hoặc \(2\) tùy thuộc vào đội nào học sinh sẽ được chỉ định. Bạn có thể in bất kỳ đội hợp lệ nào.
• Nếu không có giải pháp nào, hãy in IMPOSSIBLE.

Constraints

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

Example

Sample input

5 3
1 2
1 3
4 5

Sample output

1 2 2 1 2