#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c *x) -> decltype(cerr << *x, 2);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug &operator<<(const c &) {
    return *this;
  }
};
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
const int nax = 2007;
using bn = bitset<nax>;
int n, m;
bn tab[nax];
void test() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) tab[i].reset();
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    tab[a][b] = 1;
    tab[b][a] = 1;
  }
  int czy = 1;
  for (int i = 1; i <= n; i++) {
    if (tab[i].count() & 1) {
      czy = 0;
      tab[i][i] = 1;
      tab[i][0] = 1;
    }
  }
  if (czy) {
    printf("1\n");
    for (int i = 1; i <= n; i++) printf("1 ");
    printf("\n");
    return;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
      if (tab[j][i]) {
        swap(tab[i], tab[j]);
        break;
      }
    }
    if (!tab[i][i]) tab[i][i] = 1;
    for (int j = 1; j <= n; j++)
      if (j != i && tab[j][i]) tab[j] ^= tab[i];
  }
  printf("2\n");
  for (int i = 1; i <= n; i++) printf("%d ", tab[i][0] + 1);
  printf("\n");
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) test();
  return 0;
}
