P1021

事实上这是个暴力，DCEC 算法有时间再补吧。

#include <bits/stdc++.h>

typedef long long i64;
const int N = 100010, M = 100010;
int t, a, b, m;
struct Edges {
    int u, v;
}e[M];
int deg[N];
std::unordered_map<i64, int> rec;

i64 bipair(int x, int y) {
    return 1ll * x * N + y;
}
int query(int x, int y) {
// is x in the set of colors of edges adjacent to vertex y? 
    int z = bipair(x, y);
    if (rec.find(z) == rec.end()) {
        return 0;
    } else {
        return rec[z];
    }
    return 114514;
}
void modify(int x, int y, int ymatch) {
    rec[bipair(x, y)] = ymatch;
    return;
}
int mex(int u) {
    int x = 1;
    while (query(x, u) != 0) {
        ++ x;
    }
    return x;
}

int main(void) {
    scanf("%d", &t);
    while (t --) {
        scanf("%d%d%d", &a, &b, &m);
        for (int i = 1; i <= m; ++ i) {
            scanf("%d%d", &e[i].u, &e[i].v);
            e[i].v += a;
            ++ deg[e[i].u];
            ++ deg[e[i].v];
        }
        for (int i = 1; i <= m; ++ i) {
            int x = mex(e[i].u), y = mex(e[i].v);
            modify(x, e[i].u, e[i].v);
            modify(y, e[i].v, e[i].u);
            if (x == y) {
                continue;
            }
            int col = y, w = e[i].v;
            while (w) {
                int temp = query(x + y - col, w);
                modify(x + y - col, w, query(col, w));
                modify(col, w, temp);
                w = temp;
                col = x + y - col;
            }
        }
        int ans = 0;
        for (int i = 1; i <= a + b; ++ i) {
            ans = std::max(ans, deg[i]);
        }
        printf("%d\n", ans);
        for (int i = 1; i <= m; ++ i) {
            for (int j = 1; j <= ans; ++ j) {
                if (query(j, e[i].u) == e[i].v) {
                    printf("%d ", j);
                }
            }
        }
        puts("");
        for (int i = 1; i <= a + b; ++ i) {
            deg[i] = 0;
        }
        std::unordered_map<i64, int> newbie;
        rec.swap(newbie);
    }

    return 0;
}