F. OH NO1 (-2-3-4)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан неориентированный граф с $$$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$$$ для каждого ребра. Легко видеть, что порядок операций не имеет значения. Если существует несколько правильных ответов, выведите любой.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 10^6$$$, $$$1 \le m \le 4 \cdot 10^5$$$), обозначающие граф с $$$n$$$ вершинами и $$$3m$$$ рёбрами.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq 10^6$$$) — изначальные веса каждой вершины.

Затем следуют $$$m$$$ строк. $$$i$$$-я строка содержит три целых числа $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ ($$$1 \leq a_i < b_i < c_i \leq n$$$), обозначающие три ребра $$$(a_i,b_i)$$$, $$$(b_i,c_i)$$$ и $$$(c_i,a_i)$$$.

Обратите внимание, что граф может содержать кратные рёбра: пара $$$(x,y)$$$ может несколько раз встречаться в треугольниках.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$, и сумма $$$m$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$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)$$$ соответственно.

Пример
Входные данные
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
Примечание

В первом наборе входных данных изначальные веса равны $$$[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]$$$, поэтому все итоговые веса различны, что означает, что никакие две соседние вершины не имеют одинаковый вес.