#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using db = double;
const int mxn = 100006;
int n, m;
int a[mxn];
vi e[mxn];
bool v[mxn];
vi V;
void dfsv(int x, int p) {
  v[x] = true;
  V.push_back(x);
  for (auto i : e[x])
    if (i != p && !v[i]) dfsv(i, x);
}
bool v1[mxn];
void dfs1(int x, int p) {
  v1[x] = true;
  for (auto i : e[x])
    if (i != p)
      if (v1[i])
        throw i;
      else
        dfs1(i, x);
}
bool v2[mxn];
bool dfs2(int x, int p, int o) {
  v2[x] = true;
  for (auto i : e[x])
    if (i != p)
      if (i == o) {
        a[x] = 1;
        return true;
      } else if (!v2[i]) {
        if (dfs2(i, x, o)) {
          a[x] = 1;
          return true;
        }
      }
  return false;
}
vector<vi> c;
void dfs3(int x, int p) {
  c.back().push_back(x);
  for (auto i : e[x])
    if (i != p) dfs3(i, x);
}
void solve(int x) {
  V = {};
  dfsv(x, 0);
  int o = 0;
  try {
    dfs1(x, 0);
  } catch (int x) {
    o = x;
  }
  if (o) {
    dfs2(o, 0, o);
  } else {
    int leaf = 0;
    for (auto i : V)
      if (e[i].size() == 1) ++leaf;
    if (leaf <= 2) return;
    if (leaf >= 4) {
      for (auto i : V)
        if (e[i].size() == 1)
          a[i] = 1;
        else
          a[i] = 2;
    } else {
      int r = 0;
      for (auto i : V)
        if (e[i].size() == 3) r = i;
      assert(r);
      c = {};
      for (auto i : e[r]) {
        c.push_back({r});
        dfs3(i, r);
      }
      vi k;
      for (auto i : c) k.push_back(min(6, (int)i.size()));
      if (k[0] * k[1] + k[0] * k[2] + k[1] * k[2] <= k[0] * k[1] * k[2]) {
        const int s = 60;
        a[r] = s;
        for (int i = 0; i < 3; ++i)
          for (int j = 0; j < k[i]; ++j) a[c[i][j]] = s / k[i] * (k[i] - j);
      }
    }
  }
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) e[i] = {};
    for (int i = 0; i < m; ++i) {
      int x, y;
      scanf("%d%d", &x, &y);
      e[x].push_back(y);
      e[y].push_back(x);
    }
    fill(v, v + n + 1, false);
    fill(v1, v1 + n + 1, false);
    fill(v2, v2 + n + 1, false);
    fill(a, a + n + 1, 0);
    for (int i = 1; i <= n; ++i)
      if (!v[i]) solve(i);
    if (count(a + 1, a + n + 1, 0) == n) {
      puts("NO");
    } else {
      puts("YES");
      for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
      puts("");
    }
  }
  return 0;
}
