#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 2;
const int M = 1e4 + 2;
int x[M], y[M], cnt[N], ans[N];
bitset<N> bs[N];
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m, i, j, k, l, t;
  cin >> t;
  while (t--) {
    cin >> n >> m;
    for (i = 0; i < n; i++) {
      cnt[i] = ans[i] = 0;
      for (j = 0; j <= n; j++) {
        bs[i][j] = 0;
      }
    }
    for (i = 0; i < m; i++) {
      cin >> x[i] >> y[i];
      x[i]--;
      y[i]--;
      bs[x[i]][y[i]] = bs[y[i]][x[i]] = 1;
      cnt[x[i]] ^= 1;
      cnt[y[i]] ^= 1;
    }
    for (i = 0; i < n; i++) {
      if (cnt[i] & 1) {
        break;
      }
    }
    if (i == n) {
      cout << 1 << '\n';
      for (i = 0; i < n; i++) {
        cout << 1 << ' ';
      }
      cout << '\n';
      continue;
    }
    for (i = 0; i < n; i++) {
      if (cnt[i] & 1) {
        bs[i][i] = 1;
        bs[i][n] = 1;
      }
    }
    j = 0;
    for (i = 0; i < n; i++) {
      for (k = j; k < n; k++) {
        if (bs[k][i]) {
          break;
        }
      }
      if (k == n) {
        continue;
      }
      swap(bs[j], bs[k]);
      for (k = 0; k < n; k++) {
        if (bs[k][i] && j != k) {
          bs[k] ^= bs[j];
        }
      }
      j++;
    }
    for (i = 0; i < n; i++) {
      for (j = 0; j < n; j++) {
        if (bs[i][j]) {
          ans[j] = bs[i][n];
          break;
        }
      }
    }
    cout << 2 << '\n';
    for (i = 0; i < n; i++) {
      cout << ans[i] + 1 << ' ';
    }
    cout << '\n';
  }
}
