#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;

        if(n == 3 && m == 2){
            for(int i = 0; i < m; ++i){
                int x, y;
                cin >> x >> y;
            }
            cout << "2\n1 2\n";
            continue;
        }

        vector<pair<int, int>> edges;
        vector<int> cnt(n + 1);
        for(int i = 0; i < m; ++i){
            int u, v;
            cin >> u >> v;
            edges.push_back({u, v});
            ++cnt[u];
            ++cnt[v];
        }

        int root;
        for(int i = 1; i <= n; ++i){
            if(cnt[i] >= 2)
                root = i;
        }

        cout << "3\n";
        for(int i = 0; i < m; ++i){
            auto [u, v] = edges[i];
            if(u != root) swap(u, v);

            if(u != root && v != root){
                cout << "1 ";
            }
            else{
                if(v & 1) cout << "2 ";
                else cout << "3 ";
            }
        }
        cout << "\n";
    }
}