#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100101], path;
int vst[100101], val[100101], dp[100101][10], root;
void init(int n) {
  root = 0;
  for (int i = 1; i <= n; i++) adj[i].clear();
  for (int i = 1; i <= n; i++) vst[i] = 0, val[i] = 0;
  path.clear();
}
int dfs(int u, int fa = 0) {
  vst[u] = 1;
  for (int v : adj[u]) {
    if (v == fa) continue;
    if (vst[v]) return v;
    int t = dfs(v, u);
    if (t) return t;
  }
  return 0;
}
int rdfs(int u, int fa = 0) {
  path.push_back(u);
  vst[u] = 1;
  for (int v : adj[u]) {
    if (v == fa) continue;
    if (vst[v]) return 1;
    if (rdfs(v, u)) return 1;
  }
  path.pop_back();
  return 0;
}
void DFS(int u, int fa = 0) {
  vst[u] = 1;
  for (int i = 1; i <= 7; i++) dp[u][i] = -i * i;
  for (int v : adj[u]) {
    if (v == fa) continue;
    DFS(v, u);
    for (int i = 1; i <= 7; i++) {
      int mx = -100000002;
      for (int j = 1; j <= 7; j++) mx = max(mx, i * j + dp[v][j]);
      dp[u][i] += mx;
    }
  }
}
void getval(int u, int fa = 0) {
  for (int v : adj[u]) {
    if (v == fa) continue;
    int mx = -100000002;
    for (int j = 1; j <= 7; j++) {
      if (mx < val[u] * j + dp[v][j]) {
        mx = val[u] * j + dp[v][j];
        val[v] = j;
      }
    }
    getval(v, u);
  }
}
int calc(int u) {
  DFS(u);
  for (int i = 1; i <= 7; i++)
    if (dp[u][i] >= 0) return i;
  return 0;
}
void solve(int n) {
  for (int i = 1; i <= n; i++) vst[i] = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < 9; j++) dp[i][j] = 0;
  for (int i = 1; i <= n; i++) {
    if (vst[i]) continue;
    int x = calc(i);
    if (x) {
      val[i] = x;
      getval(i);
      puts("YES");
      for (int j = 1; j <= n; j++) printf("%d ", val[j]);
      puts("");
      return;
    }
  }
  puts("NO");
  return;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    scanf("%d %d", &n, &m);
    init(n);
    for (int i = 1; i <= m; i++) {
      int u, v;
      scanf("%d %d", &u, &v);
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
      if (vst[i]) continue;
      root = dfs(i);
      if (root) break;
    }
    if (root) {
      puts("YES");
      for (int i = 1; i <= n; i++) vst[i] = 0;
      rdfs(root);
      for (int v : path) val[v] = 1;
      for (int i = 1; i <= n; i++) printf("%d ", val[i]);
      puts("");
      continue;
    }
    solve(n);
  }
  return 0;
}
