#include <bits/stdc++.h>
using namespace std;
const signed long long llf = (signed long long)(~0ull >> 1);
const signed int inf = (signed)(~0u >> 1);
template <typename T>
T __abs(T x) {
  return (x < 0) ? (-x) : (x);
}
template <typename T>
void pfill(T* pst, const T* ped, T val) {
  for (; pst != ped; *(pst++) = val)
    ;
}
template <typename T>
void pcopy(T* pst, const T* ped, T* pv) {
  for (; pst != ped; *(pst++) = *(pv++))
    ;
}
const int N = 2048;
int n, m;
bool deg[N];
bitset<N> eq[N];
void reverse(bitset<N>& bs, int bit) {
  if (bs.test(bit))
    bs.reset(bit);
  else
    bs.set(bit);
}
inline void init() {
  scanf("%d%d", &n, &m);
  pfill(deg, deg + n, false);
  for (int i = 0; i < n; i++) eq[i].reset();
  for (int i = 1, u, v; i <= m; i++) {
    scanf("%d%d", &u, &v);
    u--, v--;
    eq[u].set(v);
    eq[v].set(u);
    reverse(eq[u], u);
    reverse(eq[v], v);
    deg[u] = !deg[u], deg[v] = !deg[v];
  }
}
void guass() {
  for (int i = 0; i < n; i++) {
    int p = -1;
    for (int j = i; j < n && p == -1; j++)
      if (eq[j].test(i)) p = j;
    if (p == -1) continue;
    swap(eq[p], eq[i]);
    swap(deg[p], deg[i]);
    for (int j = 0; j < n; j++)
      if ((j ^ i) && eq[j].test(i)) eq[j] ^= eq[i], deg[j] ^= deg[i];
  }
}
inline void solve() {
  guass();
  int r = 1;
  for (int i = 0; i < n && r == 1; i++)
    if (deg[i]) r = 2;
  printf("%d\n", r);
  for (int i = 0; i < n; i++) printf("%d ", deg[i] + 1);
  puts("");
}
int T;
int main() {
  scanf("%d", &T);
  while (T--) {
    init();
    solve();
  }
  return 0;
}
