#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(m == n * (n - 1) / 2){
            cout << 3 << "\n";
            for(int i = 1; i <= m; ++i){
                int x, y;
                cin >> x >> y;
                if(x > y) swap(x, y);
                if(x == 1){
                    cout << 1 + (y & 1) << " ";
                }
                else{
                    cout << "3" << " ";
                }
            }
            cout << "\n";
            continue;
        }

        vector<pair<int, int>> edges;
        vector<vector<bool>> b(n + 1, vector<bool>(n + 1));
        for(int i = 0; i < m; ++i){
            int x, y;
            cin >> x >> y;
            edges.push_back({x, y});
            b[x][y] = true;
            b[y][x] = true;
        }

        pair<int, int> not_exist;
        for(int i = 1; i <= n; ++i){
            for(int j = i + 1; j <= n; ++j){
                if(!b[i][j]){
                    not_exist = {i, j};
                }
            }
        }

        cout << "2\n";
        for(int i = 0; i < m; ++i){
            auto [x, y] = edges[i];
            if(x == not_exist.first || y == not_exist.first){
                cout << "1 ";
            }
            else{
                cout << "2 "; 
            }
        }
        cout << "\n";
    }
}