/*
 * author:  ADMathNoob
 * created: 05/17/24 20:37:58
 * problem: https://qoj.ac/problem/5655
 */

/*
Comments about problem:


*/

#include <bits/stdc++.h>

using namespace std;

#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  auto SolveTestCase = [&]() -> void {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n, vector<int>(n, -1));
    vector<int> deg(n);
    for (int i = 0; i < m; i++) {
      int x, y;
      cin >> x >> y;
      --x; --y;
      g[x][y] = g[y][x] = i;
      deg[x] += 1;
      deg[y] += 1;
    }
    if (m == n * (n - 1) / 2) {
      vector<int> ret(m, 3);
      for (int i = 2; i < n; i++) {
        ret[g[0][i]] = 1;
        ret[g[1][i]] = 2;
      }
      cout << 3 << '\n';
      for (int i = 0; i < m; i++) {
        cout << ret[i] << " \n"[i == m - 1];
      }
    } else {
      for (int i = 0; i < n; i++) {
        if (deg[i] < n - 1) {
          vector<int> ret(m, 2);
          for (int j = 0; j < n; j++) {
            if (g[i][j] != -1) {
              ret[g[i][j]] = 1;
            }
          }
          cout << 2 << '\n';
          for (int i = 0; i < m; i++) {
            cout << ret[i] << " \n"[i == m - 1];
          }
          return;
        }
      }
    }
  };
  
  {
    int tt;
    cin >> tt;
    for (int qq = 1; qq <= tt; qq++) {
      SolveTestCase();
    }
  }
  
  return 0;
}