Гном-Підприємець хоче започаткувати екскурсійний бізнес у Вроцлаві. Його екскурсії проводитимуться автобусом, що їздить містом, і щоразу, коли автобус проїжджатиме повз цікаву пам'ятку, через аудіосистему автобуса відтворюватиметься записаний опис цієї пам'ятки.

Гном підготував карту, що містить $N$ пам'яток, пронумерованих від $1$ до $N$, та $M$ двосторонніх вулиць, кожна з яких з'єднує пару пам'яток. Дивовижною особливістю його карти є те, що кожна пам'ятка інцидентна щонайбільше $7$ вулицям. Кожна екскурсія буде послідовністю з $3$ різних пам'яток, де кожні дві сусідні пам'ятки з'єднані вулицею.

Тепер, перш ніж обирати маршрути екскурсій, гному потрібно підготувати записані описи пам'яток і найняти професійних дикторів. Він може дозволити собі найняти лише $4$ дикторів і може записати опис для кожної пам'ятки лише один раз, залучивши одного диктора. Проте Підприємець хвилюється, що навіть голос найкращого диктора може стати монотонним для слухачів, тому він вирішив, що в жодній можливій екскурсії всі $3$ описи не можуть бути озвучені одним і тим самим диктором.

Гном ще не визначився з жодною конкретною екскурсією, а бронювання студії звукозапису вже завтра. Допоможіть йому призначити дикторів для пам'яток так, щоб у жодній можливій екскурсії всі вони не озвучувалися одним і тим самим диктором.

Вхідні дані

Перший рядок вхідних даних містить два розділені пробілом цілі числа $N$ і $M$, що позначають кількість пам'яток і кількість вулиць на карті гнома.

Наступні $M$ рядків описують вулиці, що з'єднують пам'ятки, де $i$-й рядок містить два розділені пробілом цілі числа $a_i$ та $b_i$, що позначають номери пам'яток, з'єднаних цією вулицею.

Вихідні дані

Виведіть один рядок із $N$ розділених пробілами цілих чисел $c_1, \dots, c_N$, де $c_i$ ($1 \le c_i \le 4$) позначає ідентифікатор диктора, який має записати опис $i$-ї пам'ятки.

Якщо розв'язків декілька, виведіть будь-який із них. Можна вважати, що в кожному тестовому випадку деякий розв'язок існує.

Обмеження

$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$

жодна вулиця не з'єднує пам'ятку із самою собою,

жодна пара пам'яток не з'єднана більш ніж однією вулицею,

кожна пам'ятка інцидентна щонайбільше $7$ вулицям.

Приклади

Вхідні дані 1

3 3
1 2
2 3
3 1

Вихідні дані 1

2 1 1

Вхідні дані 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

Вихідні дані 2

2 3 1 3 1 3 1 1