#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int ans[N], deg[N];
bitset<2010> mat[N];
int main(void) {
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
      mat[i].reset();
      ans[i] = 0;
      deg[i] = 0;
    }
    for (int i = 0; i < m; i++) {
      int x, y;
      scanf("%d %d", &x, &y);
      --x;
      --y;
      deg[x]++;
      deg[y]++;
      mat[x][y] = 1;
      mat[y][x] = 1;
    }
    bool flag = true;
    for (int i = 0; i < n; i++) {
      if (deg[i] % 2 == 0) continue;
      mat[i][i] = 1;
      mat[i][n] = 1;
      flag = false;
    }
    if (flag) {
      cout << 1 << endl;
      for (int i = 0; i < n; i++) printf("%d%c", 1, " \n"[i + 1 == n]);
      continue;
    }
    int row = 0;
    for (int col = 0; col < n; col++) {
      int at = -1;
      for (int x = row; x < n; x++)
        if (mat[x][col]) at = x;
      if (at == -1) {
        ans[col] = 1;
        continue;
      }
      swap(mat[row], mat[at]);
      for (int i = row + 1; i < n; i++)
        if (mat[i][col]) mat[i] = mat[i] ^ mat[row];
      row++;
    }
    for (int i = row - 1; i >= 0; i--) {
      vector<int> ntem;
      for (int j = 0; j < n; j++)
        if (mat[i][j]) {
          if (ans[j])
            mat[i][n] = mat[i][n] ^ (ans[j] - 1);
          else
            ntem.push_back(j);
        }
      assert(ntem.size() == 1);
      ans[ntem[0]] = mat[i][n] + 1;
    }
    cout << 2 << endl;
    for (int i = 0; i < n; i++) printf("%d%c", ans[i], " \n"[i + 1 == n]);
  }
  return 0;
}
