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

Гном подготовил карту, включающую $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