Вам дан неориентированный граф с \(n\) вершинами и \(3m\) рёбрами. Граф может содержать кратные рёбра, но не содержит петель.
Граф удовлетворяет следующему условию: данные рёбра можно разделить на \(m\) групп по \(3\), таких что каждая группа является треугольником.
Треугольником являются три ребра \((a,b)\), \((b,c)\) и \((c,a)\) для некоторых трёх различных вершин \(a,b,c\) (\(1 \leq a,b,c \leq n\)).
Изначально каждая вершина \(v\) имеет неотрицательный целый вес \(a_v\). Для каждого ребра \((u,v)\) в графе вы должны выполнить следующую операцию ровно один раз:
- Выбрать целое число \(x\) от \(1\) до \(4\). Затем увеличть \(a_u\) и \(a_v\) на \(x\).
После выполнения всех операций должно выполняться следующее условие: если \(u\) и \(v\) соединены ребром, то \(a_u \ne a_v\).
Можно доказать, что это всегда возможно при ограничениях задачи. Приведите способ, как это сделать, выводя выбор \(x\) для каждого ребра. Легко видеть, что порядок операций не имеет значения. Если существует несколько правильных ответов, выведите любой.
Выходные данные
Для каждого набора входных данных выведите \(m\) строк по \(3\) целых числа в каждой.
\(i\)-я строка должна содержать три целых числа \(e_{ab},e_{bc},e_{ca}\) (\(1 \leq e_{ab}, e_{bc} , e_{ca} \leq 4\)), обозначающие выбор значения \(x\) для рёбер \((a_i, b_i)\), \((b_i,c_i)\) and \((c_i, a_i)\) соответственно.
Примечание
В первом наборе входных данных изначальные веса равны \([0,0,0,0]\). Мы добавим значения следующим образом:
- Добавили \(2\) к вершинам \(1\) и \(2\)
- Добавили \(1\) к вершинам \(2\) и \(3\)
- Добавили \(3\) к вершинам \(3\) и \(1\)
Итоговые веса равны \([5,3,4,0]\). Ответ корректен, потому что \(a_1 \neq a_2\), \(a_1 \neq a_3\), \(a_2 \neq a_3\), и все выбранные значения находятся между \(1\) и \(4\).
Во втором наборе входных данных изначальные веса равны \([0,0,0,0,0]\). Веса после операций равны \([12,5,6,7,6]\). Ответ корректен, потому что \(a_1 \neq a_2\), \(a_1 \neq a_3\), \(a_2 \neq a_3\), and that \(a_1 \neq a_4\), \(a_1 \neq a_5\), \(a_4 \neq a_5\), и все выбранные значения находятся между \(1\) и \(4\).
В третьем наборе входных данных изначальные веса равны \([3,4,5,6]\). Веса после операций равны \([19,16,17,20]\), поэтому все итоговые веса различны, что означает, что никакие две соседние вершины не имеют одинаковый вес.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 1
0 0 0 0
1 2 3
5 2
0 0 0 0 0
1 2 3
1 4 5
4 4
3 4 5 6
1 2 3
1 2 4
1 3 4
2 3 4
5 4
0 1000000 412 412 412
1 2 3
1 4 5
2 4 5
3 4 5
|
2 1 3
2 3 3
4 3 3
3 1 2
2 2 3
2 3 4
3 1 1
2 3 4
1 2 4
4 4 3
4 1 1
|