#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void err() { cout << "" << endl; }
template <template <typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) {
  for (auto x : a) cout << x << ' ';
  err(args...);
}
template <typename T, typename... Args>
void err(T a, Args... args) {
  cout << a << ' ';
  err(args...);
}
const int N = 2E3 + 100;
bitset<N> b[N];
vector<int> G[N];
int n, m, x[N];
void gauss() {
  int i = 0;
  for (decay<decltype(n)>::type j = (0), _j = (n); j < _j; ++j) {
    bool ok = true;
    if (!b[i].test(j)) {
      ok = false;
      for (decay<decltype(n)>::type k = (i + 1), _k = (n); k < _k; ++k) {
        if (b[k].test(j)) {
          swap(b[i], b[k]);
          ok = true;
          break;
        }
      }
    }
    if (ok) {
      for (decay<decltype(n)>::type k = (i + 1), _k = (n); k < _k; ++k)
        if (b[k].test(j)) b[k] ^= b[i];
      i++;
    }
  }
  for (decay<decltype(n - 1)>::type i = (n - 1), _i = (-1); i > _i; --i) {
    int t = -1;
    for (decay<decltype(n)>::type j = (0), _j = (n); j < _j; ++j)
      if (b[i].test(j)) {
        if (t == -1) {
          t = j;
          x[t] = 0;
        } else
          x[t] ^= x[j];
      }
    if (b[i].test(n) && t != -1) x[t] ^= 1;
  }
}
int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> n >> m;
    fill(x, x + n, 0);
    for (decay<decltype(n)>::type i = (0), _i = (n); i < _i; ++i) {
      G[i].clear();
      b[i].reset();
    }
    for (decay<decltype(m)>::type i = (0), _i = (m); i < _i; ++i) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      G[u].push_back(v);
      G[v].push_back(u);
    }
    bool ok = true;
    for (decay<decltype(n)>::type i = (0), _i = (n); i < _i; ++i) {
      if (G[i].size() % 2) {
        ok = false;
        break;
      }
    }
    if (ok) {
      puts("1");
    } else {
      for (decay<decltype(n)>::type i = (0), _i = (n); i < _i; ++i) {
        if (G[i].size() % 2) {
          b[i].set(i);
          b[i].set(n);
        }
        for (int v : G[i]) {
          b[i].set(v);
        }
      }
      gauss();
      puts("2");
    }
    for (decay<decltype(n)>::type i = (0), _i = (n); i < _i; ++i)
      printf("%d%c", x[i] + 1, i == _i - 1 ? '\n' : ' ');
  }
}
