代码

#include <bits/stdc++.h>
using namespace std;

constexpr int M = 2010;

bitset<M> f[M];
int T, n, m, x[M];
vector<int> e[M];

inline void solve() {
    assert(scanf("%d%d", &n, &m));
    for (int i = 0; i < n; i++) x[i] = 0, f[i].reset(), e[i].clear();
    for (int i = 1, u, v; i <= m; i++) assert(scanf("%d%d", &u, &v)), u--, v--, e[u].push_back(v), e[v].push_back(u);
    bool flag = true;
    for (int i = 0; i < n; i++) {
        for (int j : e[i]) f[i][j] = 1;
        if (e[i].size() & 1) f[i][i] = f[i][n] = 1, flag = false;
    }
    if (flag) {
        printf("1\n");
        for (int i = 1; i <= n; i++) printf("%d ", 1);
        printf("\n");
        return;
    }
    for (int i = 0; i < n; i++) {
        int p = i;
        for (int j = i; j < n; j++)
            if (f[j][i]) {
                p = j;
                break;
            }
        swap(f[i], f[p]);
        for (int j = i + 1; j < n; j++)
            if (f[j][i]) f[j] ^= f[i];
    }
    for (int i = n - 1; i >= 0; i--) {
        x[i] = f[i][n];
        for (int j = i + 1; j < n; j++)
            if (f[i][j]) x[i] ^= x[j];
    }
    printf("2\n");
    for (int i = 0; i < n; i++) printf("%d ", x[i] + 1);
}

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

            if (f[j][i]) {
                p = j;
                break;
            }

这里的 break 删掉就 WA 了，不知道为什么