Good Bye 2021: 2022 is NEAR |
---|
Закончено |
Вам дан простой неориентированный граф из $$$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
Название |
---|