#include <bits/stdc++.h>
using namespace std;
const int NN = 2000;
bitset<NN> a[NN], f;
int b[NN], d[NN];
int main() {
  int T, n, m, k;
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) a[i].reset(), d[i] = 0;
    f.reset();
    for (int u, v; m--;) {
      scanf("%d %d", &u, &v);
      u--;
      v--;
      d[u]++;
      d[v]++;
      a[u][v] = a[v][u] = 1;
    }
    for (int i = 0; i < n; i++) a[i][i] = (d[i] &= 1);
    for (int i = k = 0; i < n; i++) {
      for (int j = k; j < n; j++)
        if (a[j][i]) {
          if (j != k) {
            swap(a[j], a[k]);
            swap(d[j], d[k]);
          }
          break;
        }
      if (a[k][i]) {
        for (int j = 0; j < n; j++)
          if (a[j][i] && j != k) {
            a[j] ^= a[k];
            d[j] ^= d[k];
          }
        b[k++] = i;
      }
    }
    for (int i = 0; i < k; i++) f[b[i]] = d[i];
    printf("%d\n", 2 - (f.count() == 0));
    for (int i = 0; i < n; i++) printf("%d ", 1 + f[i]);
    puts("");
  }
  return 0;
}
