F. Трехцветные треугольники
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан простой неориентированный граф из $$$n$$$ вершин и $$$m$$$ ребер. Ребро $$$i$$$ имеет цвет $$$c_i$$$, который равен $$$1$$$, $$$2$$$ или $$$3$$$, или еще не покрашено (в таком случае $$$c_i = -1$$$).

Вам нужно покрасить все еще не покрашенные ребра так, чтобы для любых трех попарно соседних вершин $$$1 \leq a < b < c \leq n$$$ цвета ребер $$$a \leftrightarrow b$$$, $$$b \leftrightarrow c$$$ и $$$a \leftrightarrow c$$$ были либо попарно различны, либо все одинаковые. В случае, если не существует подходящей раскраски, вы должны определить это.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10$$$): количество наборов входных данных.

Следующие строки содержат описания наборов входных данных.

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \leq n \leq 64$$$, $$$0 \leq m \leq \min(256, \frac{n(n-1)}{2})$$$): количество вершин и ребер в графе.

Каждая из следующих $$$m$$$ строк содержит три целых числа $$$a_i$$$, $$$b_i$$$ и $$$c_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \ne b_i$$$, $$$c_i$$$ равно $$$-1$$$, $$$1$$$, $$$2$$$ или $$$3$$$), означающих, что между вершинами $$$a_i$$$ и $$$b_i$$$ существует ребро цвета $$$c_i$$$. Гарантируется, что любая пара вершин соединена не более чем одним ребром.

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

Для каждого набора входных данных выведите $$$m$$$ целых чисел $$$d_1, d_2, \ldots, d_m$$$, где $$$d_i$$$ — цвет $$$i$$$-го ребра в вашей раскраске. Если не существует подходящей раскраски, выведите $$$-1$$$.

Пример
Входные данные
4
3 3
1 2 1
2 3 2
3 1 -1
3 3
1 2 1
2 3 1
3 1 -1
4 4
1 2 -1
2 3 -1
3 4 -1
4 1 -1
3 3
1 2 1
2 3 1
3 1 2
Выходные данные
1 2 3 
1 1 1 
1 2 2 3 
-1