Chú lùn Doanh nhân muốn khởi nghiệp kinh doanh dịch vụ hướng dẫn du lịch tại Wroclaw. Các chuyến tham quan của anh sẽ được thực hiện bằng xe buýt chạy quanh thành phố, và mỗi khi xe buýt đi qua một địa danh thú vị, một bản ghi âm thuyết minh về địa danh đó sẽ được phát qua hệ thống âm thanh trên xe.

Chú lùn đã chuẩn bị một tấm bản đồ bao gồm $N$ địa danh, được đánh số từ $1$ đến $N$, và $M$ con phố hai chiều, mỗi con phố nối một cặp địa danh. Một đặc điểm đáng ngạc nhiên trên bản đồ của anh là mỗi địa danh chỉ nối với tối đa $7$ con phố. Mỗi chuyến tham quan sẽ là một dãy gồm $3$ địa danh khác nhau, trong đó hai địa danh liên tiếp bất kỳ đều được nối với nhau bởi một con phố.

Bây giờ, trước khi chọn các chuyến tham quan, chú lùn cần chuẩn bị các bản ghi âm thuyết minh cho các địa danh và thuê các thuyết minh viên chuyên nghiệp. Anh chỉ đủ khả năng thuê $4$ thuyết minh viên, và chỉ có thể thu âm lời thuyết minh cho mỗi địa danh đúng một lần bằng một thuyết minh viên duy nhất. Tuy nhiên, Doanh nhân lo ngại rằng ngay cả giọng đọc của thuyết minh viên xuất sắc nhất cũng có thể trở nên đơn điệu đối với khán giả, vì vậy anh quyết định rằng trong bất kỳ chuyến tham quan khả dĩ nào, cả $3$ lời thuyết minh không được phép do cùng một thuyết minh viên đọc.

Chú lùn vẫn chưa quyết định bất kỳ chuyến tham quan cụ thể nào, trong khi lịch đặt phòng thu âm của anh là vào ngày mai. Hãy giúp anh phân công thuyết minh viên cho các địa danh sao cho trong bất kỳ chuyến tham quan khả dĩ nào, chúng cũng không bị thuyết minh bởi cùng một người.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $N$ và $M$ cách nhau bởi dấu cách, biểu thị số lượng địa danh và số lượng con phố trên bản đồ của chú lùn.

$M$ dòng tiếp theo mô tả các con phố nối các địa danh, trong đó dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$ cách nhau bởi dấu cách biểu thị số hiệu của hai địa danh được nối bởi con phố này.

Dữ liệu ra

In ra một dòng duy nhất gồm $N$ số nguyên $c_1, \dots, c_N$ cách nhau bởi dấu cách, trong đó $c_i$ ($1 \le c_i \le 4$) biểu thị mã số của thuyết minh viên sẽ thu âm lời thuyết minh cho địa danh thứ $i$.

Nếu có nhiều lời giải, hãy in ra bất kỳ lời giải nào. Bạn có thể giả sử rằng trong mọi test đều tồn tại ít nhất một lời giải.

Giới hạn

$1 \le N \le 10^6$

$1 \le M \le 3.5 \cdot 10^6$

$1 \le a_i, b_i \le N$

$a_i \neq b_i$

không có con phố nào nối một địa danh với chính nó,

không có cặp địa danh nào được nối bởi nhiều hơn một con phố,

mỗi địa danh nối với tối đa $7$ con phố.

Ví dụ

Dữ liệu vào 1

3 3
1 2
2 3
3 1

Dữ liệu ra 1

2 1 1

Dữ liệu vào 2

8 13
1 2
1 3
1 4
1 5
1 6
1 7
2 3
3 4
4 5
5 6
6 7
7 8
8 2

Dữ liệu ra 2

2 3 1 3 1 3 1 1