#include <bits/stdc++.h>
using namespace std;
const int N = 2002;
const int INF = (int)1e9 + 41;
const long long MD = (long long)1e9 + 7;
bool D = false;
bool u[N][N];
bool isDed[N];
int deg[N];
int col[N];
int n;
void solve1() {
  int v = -1;
  for (int i = 0; i < n; i++) {
    if (!isDed[i] && deg[i] % 2 == 1 && v == -1) {
      v = i;
    }
  }
  if (v == -1) {
    for (int i = 0; i < n; i++) {
      if (!isDed[i]) {
        col[i] = 0;
      }
    }
    return;
  }
  vector<int> w;
  for (int i = 0; i < n; i++) {
    if (u[v][i] && !isDed[i]) {
      w.push_back(i);
    }
  }
  for (int i = 0; i < (int)w.size(); i++) {
    int v2 = w[i];
    u[v2][v] = false;
    deg[v2]--;
    for (int j = 0; j < i; j++) {
      int v1 = w[j];
      if (u[v1][v2]) {
        u[v1][v2] = u[v2][v1] = false;
        deg[v1]--;
        deg[v2]--;
      } else {
        u[v1][v2] = u[v2][v1] = true;
        deg[v1]++;
        deg[v2]++;
      }
    }
  }
  isDed[v] = true;
  solve1();
  isDed[v] = false;
  int num0 = 0, num1 = 0;
  for (int i = 0; i < n; i++) {
    if (!u[v][i] || isDed[i]) continue;
    if (col[i] == 0)
      num0++;
    else
      num1++;
  }
  assert((num0 + num1) % 2 == 1);
  if (num0 % 2 == 0) col[v] = 0;
  if (num1 % 2 == 0) col[v] = 1;
}
void solve() {
  int m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      u[i][j] = false;
    }
    isDed[i] = false;
    deg[i] = 0;
    col[i] = -1;
  }
  for (int i = 0; i < m; i++) {
    int v1, v2;
    cin >> v1 >> v2;
    v1--;
    v2--;
    u[v1][v2] = u[v2][v1] = true;
    deg[v1]++;
    deg[v2]++;
  }
  solve1();
  bool is2 = false;
  for (int i = 0; i < n; i++) {
    if (col[i] == 1) is2 = true;
  }
  cout << (is2 ? "2\n" : "1\n");
  for (int i = 0; i < n; i++) {
    cout << col[i] + 1 << " ";
  }
  cout << "\n";
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}
