#include <bits/stdc++.h>
using namespace std;
bitset<2010> a[2010];
bool x[2010];
int n, m, d[2010];
void gaosi(int n) {
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++)
      if (a[j][i] == 1) {
        swap(a[j], a[i]);
        break;
      }
    if (!a[i][i]) continue;
    for (int j = i + 1; j <= n; j++)
      if (a[j][i]) a[j] ^= a[i];
  }
}
void solve(int n) {
  for (int i = n; i; i--) {
    for (int j = i + 1; j <= n; j++)
      if (a[i][j] && x[j]) a[i][n + 1] = a[i][n + 1] ^ x[j];
    x[i] = a[i][n + 1];
  }
}
void solve() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) d[i] = 0, a[i].reset();
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    d[u]++;
    d[v]++;
    a[u][v] = 1;
    a[v][u] = 1;
  }
  bool flag = 1;
  for (int i = 1; i <= n; i++)
    if (d[i] & 1) {
      flag = 0;
      a[i][i] = 1;
      a[i][n + 1] = 1;
    }
  if (flag) {
    puts("1");
    for (int i = 1; i <= n; i++) printf("%d ", 1);
    puts("");
    return;
  }
  gaosi(n);
  solve(n);
  puts("2");
  for (int i = 1; i <= n; i++) printf("%d ", x[i] + 1);
  puts("");
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) solve();
  return 0;
}
