#include <bits/stdc++.h>
const int MAXN = 2000 + 10;
int n, m;
std::bitset<MAXN> g[MAXN];
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
      g[i].reset();
    }
    static int deg[MAXN];
    memset(deg, 0, sizeof deg);
    for (int i = 1; i <= m; i++) {
      int u, v;
      scanf("%d%d", &u, &v);
      g[u][v] = g[v][u] = 1;
      deg[u]++;
      deg[v]++;
    }
    bool flag = 1;
    for (int i = 1; i <= n; i++) {
      if (deg[i] & 1) {
        flag = 0;
        g[i][i] = g[i][n + 1] = 1;
      }
    }
    if (flag) {
      printf("1\n");
      for (int i = 1; i <= n; i++) {
        printf("1 ");
      }
      printf("\n");
      continue;
    }
    for (int i = 1; i <= n; i++) {
      if (!g[i][i]) {
        for (int j = i + 1; j <= n; j++) {
          if (g[j][i]) {
            std::swap(g[i], g[j]);
            break;
          }
        }
      }
      if (!g[i][i]) continue;
      for (int j = i + 1; j <= n; j++) {
        if (g[j][i]) {
          g[j] ^= g[i];
        }
      }
    }
    std::bitset<MAXN> ans;
    ans[n + 1] = 1;
    for (int i = n; i >= 1; i--) {
      ans[i] = ((ans & g[i]).count() & 1);
    }
    printf("2\n");
    for (int i = 1; i <= n; i++) {
      printf("%d ", ans[i] + 1);
    }
    printf("\n");
  }
}
