/*
   __Allahu Akbar__
   __All_praises_to_Allah__
   __Bismillahir_Rahmanir_Rahim__

   Author: Abdullah Al Nayem
   Studying B.Sc in CSE at Leading University.

   Practice, like you've never won. Perform, like you've never lost.
   Practice hard, play hard. Be hard to beat.

*/

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <bitset>
using namespace std;

#define MAXN              100007
#define ll                long long
#define pb                push_back
#define mkp               make_pair
#define F                 first
#define S                 second
#define Sort_arr(arr,x)   sort(arr,arr+x)
#define Sortr_arr(arr,x)  sort(arr, arr+n,greater<int>())
#define SortS(str)        sort(str.begin(), str.end())
#define SortRS(str)       sort(str.rbegin(), str.rend())
#define arr_rev(n)        sort(n.begin(), n.end(), greater<int>())
#define gin(a)            getline(cin,a)
#define Sz(a)             a.size()
#define Ignore            cin.ignore()
#define sq(n)             (n*n)
#define cube(n)           (n*n*n)
#define min3(a, b, c)     min(a, min(b, c))
#define max3(a, b, c)     max(a, max(b, c))
#define YES               cout << "YES" << endl
#define NO                cout << "NO" << endl
#define pYES              printf("YES\n")
#define pNO               printf("NO\n")
#define bs                binary_search
#define lb                lower_bound
#define ub                upper_bound
#define all(a)            a.begin(),a.end()
#define Fast_read         ios_base::sync_with_stdio(false);
#define Test_case         int test_case = 1;cin>>test_case;for (int Case = 1; Case<=test_case; Case++)

vector <int> vec[MAXN], cnt(MAXN), parent(MAXN), visited(MAXN);
int totalCount = 1;

void bfs(int node)
{
    int edgeCount = 0, marker = 0;
    queue <int> q;
    q.push(node);

    while(!q.empty())
    {
        int t = q.front();
        q.pop();

        if (visited[t]) continue;
        visited[t] = true;

        if (cnt[t]%2 == 1) marker = t;
        parent[t] = 1;

        for (int i = 0; i<vec[t].size(); i++)
        {
            if (!visited[vec[t][i]]) q.push(vec[t][i]), edgeCount++;
        }
    }

    if ((edgeCount & 1) && marker) totalCount = max(totalCount, 2), parent[marker] = 2;
    else if (edgeCount & 1)
    {
        totalCount = 3;
        parent[node] = 3;
        parent[vec[node][0]] = 2;
    }
}

int main()
{
    Fast_read

    Test_case
    {
        totalCount = 1;
        for (int i = 0; i<MAXN; i++) {vec[i].clear(); cnt[i] = 0; visited[i] = 0; parent[i] = 0;}

        int n, m, x, y;
        cin >> n >> m;

        for (int i = 0; i<m; i++)
        {
            cin >> x >> y;

            vec[x].push_back(y);
            vec[y].push_back(x);

            cnt[x]++;
            cnt[y]++;
        }

        if (m%2 == 0)
        {
            cout << 1 << endl;
            for (int i = 0; i<n; i++)
            {
                cout << 1 << " ";
            }
            cout << endl;
            continue;
        }

        for (int i = 1; i<=n; i++)
        {
            if (!visited[i]) bfs(i);
        }
        cout << totalCount << endl;

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

    return 0;
}