#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 11, INF = 1e9;
vector<int> adj[N], cmp;
int dp[N][M], best[N][M], edge;
int deg[5], id1, id2, id, ans[N];
bool mark[N];
int par[N];
int vl[M], h[3];
void dfs(int v) {
  mark[v] = true;
  int degree = adj[v].size();
  edge += degree;
  if (degree >= 4) deg[4]++, id = v;
  if (degree == 3 && id1 == -1)
    id1 = v, deg[3]++;
  else if (degree == 3)
    id2 = v, deg[3]++;
  cmp.push_back(v);
  for (auto u : adj[v]) {
    if (mark[u]) continue;
    dfs(u);
  }
}
void pre_process() {
  for (int j = 1; j < M; j++) dp[1][j] = -j * j;
  for (int i = 2; i < N; i++)
    for (int j = 1; j < M; j++) {
      dp[i][j] = -INF;
      for (int k = 1; k < M; k++) {
        if (dp[i - 1][k] + k * j - j * j > dp[i][j]) best[i][j] = k;
        dp[i][j] = max(dp[i][j], dp[i - 1][k] + k * j - j * j);
      }
    }
  return;
}
void go1(int v, int p = -1) {
  par[v] = p;
  for (auto u : adj[v]) {
    if (u == p) continue;
    go1(u, v);
  }
}
int go2(int v, int p) {
  for (auto u : adj[v]) {
    if (u == p) continue;
    return go2(u, v) + 1;
  }
  return 1;
}
void go3(int v, int p, int d) {
  ans[v] = best[d][ans[p]];
  for (auto u : adj[v]) {
    if (u == p) continue;
    go3(u, v, d - 1);
  }
}
int main() {
  pre_process();
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
      int u, v;
      cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
    bool found = false;
    for (int i = 1; i <= n; i++) {
      if (found) continue;
      if (mark[i]) continue;
      memset(deg, 0, sizeof deg);
      edge = 0;
      id1 = -1, id2 = -1, id = -1;
      cmp.clear();
      dfs(i);
      edge /= 2;
      if (edge >= (int)cmp.size()) {
        found = true;
        for (auto v : cmp) ans[v] = 1;
        continue;
      }
      if (deg[4]) {
        found = true;
        ans[id] = 2;
        for (auto u : adj[id]) {
          ans[u] = 1;
        }
        continue;
      }
      if (deg[3] >= 2) {
        found = true;
        int u = id1, v = id2;
        go1(v);
        while (v != u) {
          ans[u] = 2;
          u = par[u];
        }
        ans[v] = 2;
        for (auto x : adj[v])
          if (ans[x] == 0) ans[x] = 1;
        u = id1;
        ;
        for (auto x : adj[u])
          if (ans[x] == 0) ans[x] = 1;
        continue;
      }
      if (deg[3] == 0) {
        continue;
      }
      if (deg[3] == 1) {
        int v = id1;
        for (int j = 0; j < 3; j++) h[j] = go2(adj[v][j], v);
        memset(vl, 0, sizeof vl);
        for (int k = 1; k < M; k++) {
          for (int j = 0; j < 3; j++) vl[k] += dp[h[j] + 1][k];
          vl[k] += k * k + k * k;
          if (vl[k] >= 0) {
            found = true;
            ans[v] = k;
            for (int j = 0; j < 3; j++) go3(adj[v][j], v, h[j] + 1);
            break;
          }
        }
        continue;
      }
    }
    if (found) cout << "YES\n";
    if (found)
      for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
    if (found) cout << "\n";
    if (!found) cout << "NO\n";
    for (int i = 1; i <= n; i++) mark[i] = false, adj[i].clear(), ans[i] = 0;
  }
}
