#include <bits/stdc++.h>
using namespace std;
const int MN = 2010;
int N, M;
vector<int> adj[MN];
bitset<MN> A[MN], B[MN];
int ans[MN];
void gauss() {
  for (int i = 0; i < N; i++) {
    B[i].reset();
    B[i][i] = 1;
  }
  for (int i = 0; i < N; i++) {
    for (int j = i; j < N; j++) {
      if (A[j][i]) {
        swap(A[i], A[j]);
        swap(B[i], B[j]);
        break;
      }
    }
    for (int j = i + 1; j < N; j++) {
      if (A[j][i]) {
        A[j] ^= A[i];
        B[j] ^= B[i];
      }
    }
  }
  for (int i = N - 1; i >= 0; i--) {
    for (int j = i - 1; j >= 0; j--) {
      if (A[j][i]) {
        A[j] ^= A[i];
        B[j] ^= B[i];
      }
    }
  }
}
void main2() {
  scanf("%d %d", &N, &M);
  for (int i = 0; i < N; i++) adj[i].clear();
  for (int i = 0; i < M; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    u--;
    v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  bool ok = true;
  for (int i = 0; i < N; i++)
    if (adj[i].size() % 2) {
      ok = false;
      break;
    }
  if (ok) {
    printf("1\n");
    for (int i = 0; i < N; i++) {
      printf("1 ");
    }
    printf("\n");
    return;
  }
  for (int i = 0; i < N; i++) A[i].reset();
  for (int u = 0; u < N; u++) {
    for (int i = 0; i < adj[u].size(); i++) {
      int v = adj[u][i];
      A[u][v] = 1;
    }
    if (adj[u].size() % 2) A[u][u] = 1;
  }
  gauss();
  for (int i = 0; i < N; i++) {
    ans[i] = 0;
    for (int j = 0; j < N; j++) {
      ans[i] ^= (B[i][j] & (adj[j].size() % 2));
    }
  }
  printf("2\n");
  for (int i = 0; i < N; i++) {
    printf("%d ", ans[i] + 1);
  }
  printf("\n");
}
int TC;
int main() {
  scanf("%d", &TC);
  while (TC--) main2();
}
