#include<bits/stdc++.h>
#define int long long
#define N 2010
using namespace std;

int T, n, m;
vector<int>p[N];
int a[N][N], X[N];
void Sol() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i].clear();
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n + 1; j++) a[i][j] = 0;
    for(int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        p[u].push_back(v);
        p[v].push_back(u); 
    }
    bool flag = 1;
    for(int i = 1; i <= n; i++) {
        for(auto y : p[i]) a[i][y] = 1;
        if(p[i].size() & 1) a[i][i] = a[i][n + 1] = 1, flag = 0;
    }
    if(flag) {
        cout << 1 << endl;
        for(int i = 1; i <= n; i++) cout << 1 << " ";
        cout << endl;
        return;
    }

    /*for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n + 1; j++) cout << a[i][j] << " ";
        cout << endl;
    }
    cout << endl;*/
    int r = 1;
    for(int i = 1; i <= n; i++) {
        int Get = 0;
        for(int j = r; j <= n; j++)
            if(a[j][i]) {
                Get = j;
                break;
            }
        if(Get == 0) continue;
        swap(a[r], a[Get]);
        for(int j = 1; j <= n; j++) {
            if(j == r || !a[j][i]) continue;
            for(int k = 1; k <= n + 1; k++) a[j][k] ^= a[i][k];
        }
        /*cout << i << " : " << endl;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n + 1; j++) cout << a[i][j] << " ";
            cout << endl;
        }
        cout << endl;*/
        r++;
    }r--;
    /*cout << "r : " << r << endl;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n + 1; j++) cout << a[i][j] << " ";
        cout << endl;
    }*/

    for(int i = 1; i <= n; i++) X[i] = 1;
    for(int i = 1; i <= r; i++) {
        for(int j = 1; j <= n; j++) {
            if(a[i][j]) {
                if(a[i][n + 1]) X[j] = 2;
                break;
            }
        }
    }

    
    cout << 2 << endl;
    for(int i = 1; i <= n; i++) cout << X[i] << " ";
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> T;
    while(T--) Sol();
    return 0;
}
/*
1
6 5
1 2
2 3
3 4
4 2
4 1
*/