В Берляндии приближается государственный праздник — День Флага. В честь этого события Президент страны решил устроить большой танцевальный вечер, организацию которого он поручил вашему агентству. При этом он поставил несколько условий:
В распоряжении агенства есть 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
| Codeforces Round 207 (Div. 2) |
|---|
| Закончено |
