B. День Флага
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В Берляндии приближается государственный праздник — День Флага. В честь этого события Президент страны решил устроить большой танцевальный вечер, организацию которого он поручил вашему агентству. При этом он поставил несколько условий:

  • всего должны быть исполнены m танцев;
  • в каждом танце должны участвовать ровно три человека;
  • в каждом танце должен участвовать один танцор в белой форме, один танцор в красной форме и один танцор в синей форме (это цвета государственного флага Берляндии).

В распоряжении агенства есть n танцоров, причем, их число может быть меньше, чем 3m. То есть, какие-то танцоры, возможно, будут участвовать более чем в одном танце, но при этом они все должны быть задействованы. Однако, если в каком-то танце участвуют два или более танцоров, которые уже танцевали ранее, то этот танец перестает быть зрелищным. Ваше агентство не может этого допустить, поэтому в каждом танце участвует максимум один танцор, который танцевал ранее.

На основании всех этих критериев был составлен план из m танцев: на каждый танец было определено по три танцора, которые будут в нем участвовать. Вам же было поручено определить для каждого из n танцоров цвет формы так, чтобы выполнялось третье условие Президента: в каждом танце должен быть танцор в белой форме, танцор в красной форме и танцор в синей форме. При этом танцоры не могут менять свою форму между танцами.

Входные данные

В первой строке через пробел заданы два целых числа n (3 ≤ n ≤ 105) и m (1 ≤ m ≤ 105) — количество танцоров и количество танцев соответственно. Далее идёт m строк, описывающих танцы в порядке их исполнения. В i-ой строке находятся три различных целых числа — номера танцоров, участвующих в i-ом танце. Танцоры пронумерованы от 1 до n. Каждый танцор принимает участие хотя бы в одном танце.

Выходные данные

Выведите через пробел n чисел: i-ое из этих чисел должно обозначать цвет формы i-го танцора (1 — белый, 2 — красный, 3 — синий). Если подходящих решений несколько, выведите любое из них. Гарантируется, что хотя бы одно решение существует.

Примеры
Входные данные
7 3
1 2 3
1 4 5
4 6 7
Выходные данные
1 2 3 3 2 2 1 
Входные данные
9 3
3 6 9
2 5 8
1 4 7
Выходные данные
1 1 1 2 2 2 3 3 3 
Входные данные
5 2
4 1 5
3 1 2
Выходные данные
2 3 1 1 3