#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e3 + 10;
const int MOD = 998244353;
int n, m;
vector<int>v[N];
int ans[N];
int ind[N];
void solve() {
cin >> n >> m;
for (int i = 1; i <= m; i++) ans[i] = 0;
for (int i = 1; i <= n; i++) v[i].clear(), ind[i] = 0;
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
v[x].push_back(i);
v[y].push_back(i);
ind[x]++, ind[y]++;
}
if (n == 3)
{
cout << m << "\n";
for (int j = 1; j <= m; j++) cout << j << " ";
cout << "\n";
return;
}
if (m == n * (n - 1) / 2)
{
ans[v[1][0]] = 1;
for (int i = 1; i < v[1].size(); i++)
ans[v[1][i] = 2;
cout << "3\n";
for (int i = 1; i <= m; i++)
{
if (!ans[i]) ans[i] = 3;
cout << ans[i] << " ";
}
cout << "\n";
return;
}
cout << "2\n";
int minn = 1;
for (int i = 1; i <= n; i++)
if (ind[i] < ind[minn]) minn = i;
for (auto y : v[minn]) ans[y] = 1;
for (int i = 1; i <= m; i++)
{
if (!ans[i]) ans[i] = 2;
cout << ans[i] << " ";
}
cout << "\n";
}
int main()
{
int tt = 1;
cin >> tt;
while (tt--)
solve();
//system("pause");
return 0;
}