#include <bits/stdc++.h>
using namespace std;
namespace Base {
const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
const long long infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
template <typename T>
void read(T &x) {
  x = 0;
  int fh = 1;
  double num = 1.0;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') fh = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  if (ch == '.') {
    ch = getchar();
    while (isdigit(ch)) {
      num /= 10;
      x = x + num * (ch - '0');
      ch = getchar();
    }
  }
  x = x * fh;
}
template <typename T>
void chmax(T &x, T y) {
  x = x < y ? y : x;
}
template <typename T>
void chmin(T &x, T y) {
  x = x > y ? y : x;
}
}  // namespace Base
using namespace Base;
const int N = 100010;
struct Node {
  int data, next;
} e[N * 2];
int co[N], id[N], num, n, use[N], head[N], place, deg[N], cnt, flag, m, exist,
    size[N], tmp[N], tmp2[N], exist2, tmp3[N], exist3;
void build(int u, int v) {
  e[++place].data = v;
  e[place].next = head[u];
  head[u] = place;
}
void print1(int x) {
  printf("YES\n");
  for (int i = 1; i <= n; i++) co[i] = 0;
  for (int i = 1; i <= num; i++) co[id[i]] = 1;
  for (int i = 1; i <= n; i++) printf("%d%c", co[i], (i == n) ? '\n' : ' ');
}
void print2(int x) {
  printf("YES\n");
  for (int i = 1; i <= n; i++) co[i] = 0;
  for (int i = 1; i <= num; i++)
    if (deg[id[i]] == 1)
      co[id[i]] = 1;
    else
      co[id[i]] = 2;
  for (int i = 1; i <= n; i++) printf("%d%c", co[i], (i == n) ? '\n' : ' ');
}
void print3(int x) {
  printf("YES\n");
  for (int i = 1; i <= n; i++) co[i] = 0;
  for (int i = 1; i <= num; i++) co[id[i]] = 1;
  co[exist] = 3;
  for (int ed = head[exist]; ed != 0; ed = e[ed].next) co[e[ed].data] = 2;
  for (int i = 1; i <= n; i++) printf("%d%c", co[i], (i == n) ? '\n' : ' ');
}
void print4(int x) {
  printf("YES\n");
  for (int i = 1; i <= n; i++) co[i] = 0;
  for (int i = 1; i <= num; i++) co[id[i]] = 1;
  co[exist2] = 4;
  for (int ed = head[exist2]; ed != 0; ed = e[ed].next) {
    co[e[ed].data] = 3;
    int cnt = 0;
    for (int ed2 = head[e[ed].data]; ed2 != 0; ed2 = e[ed2].next)
      if (e[ed2].data != exist2) co[e[ed2].data] = 2, cnt++;
    if (cnt == 0) co[e[ed].data] = 2;
  }
  for (int i = 1; i <= n; i++) printf("%d%c", co[i], (i == n) ? '\n' : ' ');
}
void print5(int x) {
  printf("YES\n");
  for (int i = 1; i <= n; i++) co[i] = 0;
  for (int i = 1; i <= num; i++) co[id[i]] = 1;
  co[exist3] = 6;
  for (int ed = head[exist3]; ed != 0; ed = e[ed].next) {
    int cnt = 0;
    for (int ed2 = head[e[ed].data]; ed2 != 0; ed2 = e[ed2].next)
      if (e[ed2].data != exist3) cnt++;
    if (cnt == 0) {
      co[e[ed].data] = 3;
      continue;
    }
    int now = e[ed].data, las = exist3;
    bool f = true;
    while (co[las] > 2) {
      f = false;
      co[now] = co[las] - 1;
      for (int ed2 = head[now]; ed2 != 0; ed2 = e[ed2].next)
        if (e[ed2].data != las) {
          las = now;
          now = e[ed2].data;
          f = true;
          break;
        }
      if (f == false && co[now] != 2) {
        co[now] = 2, co[las] = 4;
        break;
      }
    }
  }
  for (int i = 1; i <= n; i++) printf("%d%c", co[i], (i == n) ? '\n' : ' ');
}
void tarjan(int x, int fa) {
  use[x] = true;
  cnt += (deg[x] == 1);
  id[++num] = x;
  size[x] = 1;
  tmp[x] = 0;
  tmp2[x] = 0;
  tmp3[x] = 0;
  for (int ed = head[x]; ed != 0; ed = e[ed].next)
    if (e[ed].data != fa) {
      if (use[e[ed].data] == true) {
        flag = true;
        print1(x);
        return;
      } else {
        tarjan(e[ed].data, x);
        size[x] += size[e[ed].data];
        if (size[e[ed].data] > 4)
          tmp3[x]++;
        else if (size[e[ed].data] > 2)
          tmp2[x]++;
        else if (size[e[ed].data] > 1)
          tmp[x]++;
        if (flag) return;
      }
    }
}
int main() {
  int op;
  read(op);
  while (op--) {
    read(n);
    read(m);
    for (int i = 1; i <= n; i++) head[i] = use[i] = deg[i] = 0;
    place = 0;
    for (int i = 1; i <= m; i++) {
      int u, v;
      read(u);
      read(v);
      build(u, v);
      build(v, u);
      deg[u]++, deg[v]++;
    }
    flag = false;
    for (int i = 1; i <= n; i++)
      if (use[i] == false) {
        cnt = 0;
        num = 0;
        exist = 0;
        exist2 = 0;
        exist3 = 0;
        tarjan(i, 0);
        if (flag == true) break;
        if (cnt >= 4) {
          flag = true;
          print2(i);
          break;
        }
        for (int j = 1; j <= num; j++) {
          if (size[id[j]] + 4 < num)
            tmp3[id[j]]++;
          else if (size[id[j]] + 2 < num)
            tmp2[id[j]]++;
          else if (size[id[j]] + 1 < num)
            tmp[id[j]]++;
          if (tmp[id[j]] + tmp2[id[j]] + tmp3[id[j]] > 2) exist = id[j];
          if (tmp2[id[j]] + tmp3[id[j]] > 1 && deg[id[j]] > 2) exist2 = id[j];
          if (tmp3[id[j]] > 0 && tmp[id[j]] + tmp2[id[j]] > 0 && deg[id[j]] > 2)
            exist3 = id[j];
        }
        if (exist) {
          flag = true;
          print3(i);
          break;
        }
        if (exist2) {
          flag = true;
          print4(i);
          break;
        }
        if (exist3) {
          flag = true;
          print5(i);
          break;
        }
      }
    if (flag == false) printf("NO\n");
  }
  return 0;
}
