#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 2007;
int n, m;
vector<int> es[MAXN];
bitset<MAXN> bs[MAXN];
bool hv[MAXN];
int dp[MAXN];
void init();
void input();
void work();
int main() {
  init();
  int T;
  scanf("%d", &T);
  while (T--) {
    input();
    work();
  }
}
void init() { ios::sync_with_stdio(false); }
void input() {
  scanf("%d%d", &n, &m);
  int u, v;
  for (int i = 1; i <= n; ++i) es[i].clear();
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &u, &v);
    es[u].push_back(v);
    es[v].push_back(u);
  }
}
void work() {
  bool flag = true;
  for (int i = 1; i <= n; ++i) {
    if (es[i].size() & 1) {
      flag = false;
      break;
    }
  }
  if (flag) {
    printf("1\n");
    for (int i = 1; i <= n; ++i) printf("1 ");
    putchar('\n');
    return;
  }
  bitset<MAXN> nb;
  memset(hv, false, sizeof(hv));
  for (int i = 1; i <= n; ++i) bs[i] = 0;
  for (int i = 1; i <= n; ++i) {
    nb = 0;
    for (auto x : es[i]) nb[x] = 1;
    nb[i] = es[i].size() & 1;
    nb[n + 1] = es[i].size() & 1;
    for (int j = 1; j <= n; ++j) {
      if (nb[j]) {
        if (hv[j])
          nb ^= bs[j];
        else {
          hv[j] = true;
          bs[j] = nb;
          break;
        }
      }
    }
  }
  memset(dp, 0, sizeof(dp));
  for (int i = n; i > 0; --i) {
    if (hv[i]) {
      dp[i] = bs[i][n + 1];
      for (int j = i + 1; j <= n; ++j) {
        if (bs[i][j] && hv[j]) dp[i] ^= dp[j];
      }
    }
  }
  printf("2\n");
  for (int i = 1; i <= n; ++i) printf("%d ", dp[i] + 1);
  putchar('\n');
}
