#include <bits/stdc++.h>
using namespace std;
int t, n, m;
bitset<2005> a[2005];
int read() {
  int x = 0, fl = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') fl = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * fl;
}
void gauss() {
  for (int i = 1; i <= n; i++) {
    if (!a[i][i]) {
      for (int j = i + 1; j <= n; j++) {
        if (a[j][i]) {
          swap(a[i], a[j]);
          break;
        }
      }
    }
    for (int j = 1; j <= n; j++)
      if (a[j][i] && j != i) a[j] ^= a[i];
  }
  return;
}
int main() {
  t = read();
  while (t--) {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) a[i].reset();
    for (int i = 1; i <= m; i++) {
      int x = read(), y = read();
      a[x].flip(y), a[y].flip(x), a[x].flip(x), a[y].flip(y), a[x].flip(n + 1),
          a[y].flip(n + 1);
    }
    int fl = 1;
    for (int i = 1; i <= n; i++) fl &= (!a[i][i]);
    if (fl) {
      puts("1");
      for (int i = 1; i <= n; i++) printf("1 ");
      putchar('\n');
      continue;
    }
    gauss();
    puts("2");
    for (int i = 1; i <= n; i++) printf("%d ", (int)a[i][n + 1] + 1);
    putchar('\n');
  }
  return 0;
}
