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

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";
    }
}

answer.code: In function ‘int main()’:
answer.code:26:9: error: ‘function’ was not declared in this scope
   26 |         function<int(int)> get_par = [&](int x){
      |         ^~~~~~~~
answer.code:5:1: note: ‘std::function’ is defined in header ‘<functional>’; did you forget to ‘#include <functional>’?
    4 | #include <vector>
  +++ |+#include <functional>
    5 | 
answer.code:26:18: error: expected primary-expression before ‘int’
   26 |         function<int(int)> get_par = [&](int x){
      |                  ^~~
answer.code: In lambda function:
answer.code:32:17: error: ‘get_par’ was not declared in this scope; did you mean ‘getchar’?
   32 |             a = get_par(a), b = get_par(b);
      |                 ^~~~~~~
      |                 getchar