#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <functional>

using namespace std;
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t--){
        int n, m;
        cin >> n >> m;

        vector<int> sz(n + 1), par(n + 1);
        for(int i = 1; i <= n; ++i){
            sz[i] = 1;
            par[i] = i;
        }

        function<int(int)> get_par = [&](int x){
            if(par[x] == x) return x;
            return par[x] = get_par(par[x]);
        };

        auto unite = [&](int a, int b){
            a = get_par(a), b = get_par(b);
            if(a == b) return false;
            if(sz[a] < sz[b]) swap(a, b);
            sz[a] += sz[b];
            par[b] = a;
            return true;
        };

        int cnt_e = 0, cnt_c = 2;
        vector<int> ans;
        for(int i = 0; i < m; ++i){
            int u, v;
            cin >> u >> v;

            if(unite(u, v)){
                if(cnt_e & 1){
                    ans.push_back(1);
                }
                else{
                    ans.push_back(2);
                }
                ++cnt_e;
            }
            else{
                ans.push_back(++cnt_c);
            }
        }

        cout << cnt_c << "\n";
        for(int x: ans)
            cout << x << " ";
        cout << "\n";
    }
}