#include <bits/stdc++.h>
using namespace std;
const int N = 2333;
int n, m;
bool deg[N];
bitset<N> eq[N];
void Reverse(bitset<N> &bs, int bit) {
  if (bs.test(bit))
    bs.reset(bit);
  else
    bs.set(bit);
}
void Init() {
  scanf("%d%d", &n, &m);
  memset(deg, 0, sizeof deg);
  for (int i = 0; i < n; i++) eq[i].reset();
  for (int i = 1, u, v; i <= m; i++) {
    scanf("%d%d", &u, &v);
    u--, v--;
    eq[u].set(v);
    eq[v].set(u);
    Reverse(eq[u], u);
    Reverse(eq[v], v);
    deg[u] = !deg[u], deg[v] = !deg[v];
  }
}
void Guass(void) {
  for (int i = 0; i < n; i++) {
    int p = -1;
    for (int j = i; j < n && p == -1; j++)
      if (eq[j].test(i)) p = j;
    if (p == -1) continue;
    swap(eq[p], eq[i]);
    swap(deg[p], deg[i]);
    for (int j = 0; j < n; j++)
      if ((j ^ i) && eq[j].test(i)) eq[j] ^= eq[i], deg[j] ^= deg[i];
  }
}
void Solve(void) {
  Guass();
  int r = 1;
  for (int i = 0; i < n && r == 1; i++)
    if (deg[i]) r = 2;
  printf("%d\n", r);
  for (int i = 0; i < n; i++) printf("%d ", deg[i] + 1);
  puts("");
}
int T;
int main(void) {
  scanf("%d", &T);
  while (T--) {
    Init();
    Solve();
  }
  return 0;
}
