Вам дан простой неориентированный граф из \(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\) были либо попарно различны, либо все одинаковые. В случае, если не существует подходящей раскраски, вы должны определить это.
Выходные данные
Для каждого набора входных данных выведите \(m\) целых чисел \(d_1, d_2, \ldots, d_m\), где \(d_i\) — цвет \(i\)-го ребра в вашей раскраске. Если не существует подходящей раскраски, выведите \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|