#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937 eng(seed);
long long random2() { return (1ll << 31ll) * eng() + eng(); }
long long n, m, k, q, T;
const long long big = 1000000007;
const long long big2 = 1000000009;
const long long mod = 998244353;
const int MAXN = 300001;
vector<vector<int> > C(MAXN, vector<int>());
long long A[MAXN] = {0};
int CC[MAXN] = {0};
int cc = 0;
bool comp(long long i, long long j) {
  return (int)(C[i]).size() > (int)(C[j]).size();
}
bool mark1[MAXN] = {0};
int par[MAXN] = {0};
vector<int> I;
int cyc1 = -1;
int cyc2 = -1;
void dfs1(int i) {
  CC[i] = cc;
  if (mark1[i]) return;
  mark1[i] = 1;
  I.push_back(i);
  for (auto& y : C[i]) {
    if (y == par[i]) continue;
    if (mark1[y]) {
      if (cyc1 == -1) {
        cyc1 = i;
        cyc2 = y;
      }
      continue;
    }
    par[y] = i;
    dfs1(y);
  }
}
bool mark2[MAXN] = {0};
void dfs2(int i) {
  if (mark2[i]) return;
  mark2[i] = 1;
  for (auto& y : C[i]) {
    if (!mark2[y]) {
      par[y] = i;
      dfs2(y);
    }
  }
}
void fill_path(int from, int to, int with) {
  while (1) {
    A[from] = with;
    if (from == to) break;
    from = par[from];
  }
}
void fill_around(int i, int x, int with) {
  for (auto& y : C[i]) {
    if (A[y] == 0 && x > 0) {
      A[y] = with;
      x--;
    }
  }
}
map<long long, pair<int, int> > M;
pair<int, int> dp(long long i, long long prev, long long par) {
  if (prev <= 1 && (int)(C[i]).size() != 3) return {0, 0};
  long long h = i * n * 1234 + prev * n + par;
  if (M.find(h) != M.end()) return M[h];
  long long lim = prev;
  if ((int)(C[i]).size() == 3) lim = 11;
  pair<int, int> best = {-big, 0};
  for (int val = 0; val < (lim); ++val) {
    if (val == 0 && (int)(C[i]).size() == 3) continue;
    int num = val * prev - val * val;
    for (auto& y : C[i]) {
      if (y != par) {
        num += dp(y, val, i).first;
      }
    }
    if (num > best.first) best = {num, val};
  }
  M[h] = best;
  return best;
}
void get_ans(long long i, long long prev, long long par) {
  long long h = i * n * 1234 + prev * n + par;
  if (M.find(h) == M.end()) return;
  pair<int, int> nxt = M[h];
  A[i] = nxt.second;
  for (auto& y : C[i]) {
    if (y != par) {
      get_ans(y, A[i], i);
    }
  }
}
void print_ans() {
  cout << "YES\n";
  for (int c1 = 0; c1 < (n); ++c1) {
    if (CC[c1] != cc) A[c1] = 0;
    cout << A[c1] << " ";
  }
  cout << "\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long a, b, c, d, e;
  cin >> T;
  for (int _ = 0; _ < (T); ++_) {
    cin >> n >> m;
    for (int c1 = 0; c1 < (n); ++c1) {
      C[c1].clear();
      mark1[c1] = 0;
      mark2[c1] = 0;
      A[c1] = 0;
      par[c1] = -1;
      CC[c1] = cc;
    }
    M.clear();
    for (int c1 = 0; c1 < (m); ++c1) {
      cin >> a >> b;
      a--;
      b--;
      C[a].push_back(b);
      C[b].push_back(a);
    }
    bool solved = 0;
    for (int c1 = 0; c1 < (n); ++c1) {
      if (!mark1[c1]) {
        I.clear();
        cyc1 = -1;
        cyc2 = -1;
        dfs1(c1);
        if (cyc1 != -1) {
          fill_path(cyc1, cyc2, 1);
          print_ans();
          solved = 1;
          break;
        }
        sort(I.begin(), I.end(), comp);
        int i = I[0];
        if ((int)(I).size() <= 1) continue;
        int j = I[1];
        if ((int)(C[i]).size() <= 2) {
          continue;
        }
        if ((int)(C[i]).size() > 3) {
          A[i] = 2;
          fill_around(i, 4, 1);
          print_ans();
          solved = 1;
          break;
        }
        if ((int)(C[j]).size() < 3) {
          pair<int, int> thing = dp(i, 0, -1);
          if (thing.first >= 0) {
            get_ans(i, 0, -1);
            print_ans();
            solved = 1;
            break;
          }
          for (auto& y : I) {
            A[y] = 0;
          }
          continue;
        }
        dfs2(i);
        fill_path(j, i, 2);
        fill_around(i, 2, 1);
        fill_around(j, 2, 1);
        print_ans();
        solved = 1;
        break;
      }
    }
    if (!solved) {
      cout << "NO\n";
    }
  }
  return 0;
}
