#include <bits/stdc++.h>
using namespace std;
const int NN = 101010;
int vst[NN], qf, qb, q[NN * 2], val[NN], sz[NN];
vector<int> adj[NN];
int main() {
  int T, n, m, u, v;
  for (cin >> T; T--;) {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
      scanf("%d%d", &u, &v);
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
    int flag = 1;
    for (int i = 1; i <= n; i++) val[i] = 0;
    for (int i = 1; i <= n; i++)
      if (!vst[i]) {
        qf = qb = 0;
        q[qb++] = i;
        vst[i] = 1;
        int edge = 0, cnt = 0, mx = 0, root = 0;
        while (qf < qb) {
          int u = q[qf++];
          edge += adj[u].size();
          if (adj[u].size() == 1) cnt++;
          if (adj[u].size() > mx) mx = adj[u].size(), root = u;
          for (int v : adj[u])
            if (!vst[v]) {
              vst[v] = 1;
              q[qb++] = v;
            }
        }
        if (qb <= edge / 2) {
          flag = 0;
          for (int i = 0; i < qb; i++) val[q[i]] = 1;
          break;
        }
        if (cnt >= 4) {
          flag = 0;
          for (int i = 0; i < qb; i++) val[q[i]] = 1 + (adj[q[i]].size() > 1);
          break;
        }
        if (cnt <= 2) continue;
        qf = qb = 0;
        q[qb++] = root;
        q[qb++] = 0;
        while (qf < qb) {
          int u = q[qf++], pa = q[qf++];
          for (int &v : adj[u])
            if (v == pa) {
              swap(adj[u].back(), v), adj[u].pop_back();
              break;
            }
          for (int v : adj[u]) q[qb++] = v, q[qb++] = u;
        }
        for (int i = qb - 1; i; i--) {
          int u = q[i];
          sz[u] = 1;
          for (int v : adj[u]) sz[u] += sz[v];
        }
        sort(adj[root].begin(), adj[root].end(),
             [&](int u, int v) { return sz[u] < sz[v]; });
        int u = adj[root][0], v = adj[root][1], w = adj[root][2];
        if (sz[u] > 1) {
          flag = 0;
          val[root] = 3;
          val[u] = val[v] = val[w] = 2;
          val[adj[u][0]] = val[adj[v][0]] = val[adj[w][0]] = 1;
          break;
        }
        if (sz[v] == 2) {
          if (sz[w] < 5) continue;
          val[u] = 3;
          val[v] = 4;
          val[adj[v][0]] = 2;
          val[root] = 6;
          for (int i = 5, t = w; i; i--) {
            val[t] = i;
            if (i > 1) t = adj[t][0];
          }
          flag = 0;
          break;
        }
        if (sz[v] > 2) {
          val[root] = 4;
          val[u] = 2;
          for (int i = 3, t = v; i; i--) {
            val[t] = i;
            if (i > 1) t = adj[t][0];
          }
          for (int i = 3, t = w; i; i--) {
            val[t] = i;
            if (i > 1) t = adj[t][0];
          }
          flag = 0;
          break;
        }
      }
    if (flag)
      puts("NO");
    else {
      puts("YES");
      for (int i = 1; i <= n; i++) printf("%d%c", val[i], " \n"[i == n]);
    }
    for (int i = 1; i <= n; i++) adj[i].clear(), vst[i] = 0;
  }
  return 0;
}
