闲话：
这是一道搞笑且神秘的题目，不难注意到题目中有 $\text{NO}$（一氧化氮），有 $\text{NO}_2$（二氧化氮），有 $\text{NO}_3^{~-}$（硝酸根），但是并不存在 $\text{NO}_4$ 这种东西，因此出题人在提示我们这题只需要用到 $1,2,3$ 三种赋值。

这种三元环图很神秘，而且 $d_i$ 的限制很难整，那就扔掉 $d_i$ 的限制。
考虑如果给三条边分别赋值 $1,2,3$，那么三个点就会加上：$3,4,5$，直接生成了一个满足条件的三元环。
类似无向图三元环计数，给每条边“定向”，即从度数小的连向度数大的，那么每个点加上的点权刚好等于入度 $+3$。
考虑用一个优先队列，每次取出当前点权最小的点，然后往外扩展给周围的邻居点权 $+1$（入度）。
但是注意三元环上的点，本身就要 $+3$。

实际上有 $d_i$ 限制也是同理的，因为题目保证有解，直接跑上面那个做法就行了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 15, M = N << 2;
int T, n, m;
int h[N], e[M], w[M], ne[M], idx = 0, col = 0;
bool st[M];
void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }
void addedge(int a, int b, int c) { add(a, b, c), add(b, a, 0); }

int a[N][5], d[N], cnt[5];
bool vis[N];
priority_queue< pair<int, int> > q;
void dijk() {
    for (int i = 1; i <= n; i++) q.push({-d[i], i}), vis[i] = 0;
    while (q.size()) {
        int dis = q.top().first, u = q.top().second; q.pop();
        if (-dis != d[u]) { q.push({-d[u], u}); continue; }
        vis[u] = 1;
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i]; if (vis[v]) continue;
            d[v]++;
            if (w[i]) st[w[i]] = 1; //反向边就不算
        }
    }
}

void print(int x, int y) {
    if (x > y) swap(x, y);
    if (x == 0 && y == 1) putchar('1');
    else if (x == 0 && y == 2) putchar('2');
    else if (x == 1 && y == 2) putchar('3');
}

void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) h[i] = -1, scanf("%d", &d[i]); idx = col = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= 3; j++) scanf("%d", &a[i][j]), d[a[i][j]] += 3;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= 3; j++) st[++col] = 0, addedge(a[i][j], a[i][j % 3 + 1], col);
    dijk();

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= 3; j++) cnt[j] = 0;
        for (int j = 1; j <= 3; j++)
            if (st[(i - 1) * 3 + j]) cnt[j % 3 + 1]++;
            else cnt[j]++;
        for (int j = 1; j <= 3; j++) print(cnt[j], cnt[j % 3 + 1]), putchar(' ');
        puts("");
    }
}

int main() {
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}