#include <bits/stdc++.h>
void work(void) {
  int n, m;
  scanf("%d%d", &n, &m);
  constexpr int N(2005);
  static std::bitset<N> a[N];
  for (int i(1); i <= n; ++i) a[i].reset();
  for (int i(0), x, y; i < m; ++i) {
    scanf("%d%d", &x, &y);
    a[x][x].flip(), a[x][y].flip(), a[x][0].flip();
    a[y][x].flip(), a[y][y].flip(), a[y][0].flip();
  }
  bool flag1(1);
  for (int i(1); i <= n; ++i)
    if (a[i].test(0)) {
      flag1 = 0;
      break;
    }
  if (flag1) {
    puts("1");
    for (int i(1); i <= n; ++i) putchar('1'), putchar(' ');
    putchar('\n');
    return;
  }
  puts("2");
  for (int i(1); i <= n; ++i) {
    int id(i);
    for (int j(i); j <= n; ++j)
      if (a[j].test(i)) {
        id = j;
        break;
      }
    if (a[id].test(i)) {
      if (id != i) std::swap(a[i], a[id]);
      for (int j(i + 1); j <= n; ++j)
        if (a[j][i]) a[j] ^= a[i];
    }
  }
  static bool val[N];
  for (int i(n); i; --i) {
    if (a[i][i]) {
      val[i] = a[i][0];
      for (int j(i + 1); j <= n; ++j) a[i][j] && (val[i] ^= val[j]);
    }
  }
  for (int i(1); i <= n; ++i) printf("%d ", val[i] + 1);
  putchar('\n');
}
int main(void) {
  int T;
  scanf("%d", &T);
  for (; T; --T) work();
  return 0;
}
