#include <bits/stdc++.h>
using namespace std;
long long dp[100005][11][2];
vector<pair<int, pair<int, int> > > zip[100005][11][2];
int t, n, m;
vector<int> edge[100005];
int par[100005], ran[100005];
void init(int n) {
  for (int i = 0; i < n; i++) par[i] = i, ran[i] = 0;
}
int find(int x) {
  if (x == par[x])
    return x;
  else
    return par[x] = find(par[x]);
}
void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;
  if (ran[x] < ran[y])
    par[x] = y;
  else {
    par[y] = x;
    if (ran[x] == ran[y]) ran[x]++;
  }
}
bool same(int x, int y) { return find(x) == find(y); }
int cnt[100005], cnte[100005], ans[100005];
;
bool connect[100005];
void dfs(int v, int u) {
  for (int i = 0; i < edge[v].size(); i++) {
    if (edge[v][i] == u) continue;
    dfs(edge[v][i], v);
  }
  for (int num = 0; num <= 10; num++) {
    long long t[4][2];
    vector<pair<int, pair<int, int> > > vec[4][2];
    int cur = 0;
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 2; j++) t[i][j] = -1e18;
    t[0][0] = 0;
    for (int i = 0; i < edge[v].size(); i++) {
      if (edge[v][i] == u) continue;
      for (int j = 0; j <= 10; j++)
        for (int k = 0; k < 2; k++) {
          if (dp[edge[v][i]][j][k] < -1e17) continue;
          for (int a = 0; a < 2; a++) {
            if (t[cur][a] < -1e17) continue;
            if (t[cur + 1][k | a] <
                t[cur][a] + dp[edge[v][i]][j][k] + 1LL * j * num) {
              t[cur + 1][k | a] =
                  max(t[cur + 1][k | a],
                      t[cur][a] + dp[edge[v][i]][j][k] + 1LL * j * num);
              vec[cur + 1][k | a] = vec[cur][a];
              vec[cur + 1][k | a].push_back(
                  make_pair(edge[v][i], make_pair(j, k)));
            }
          }
        }
      cur++;
    }
    dp[v][num][0 | !!num] =
        max(dp[v][num][0 | !!num], t[cur][0] - 1LL * num * num);
    zip[v][num][0 | !!num] = vec[cur][0];
    dp[v][num][1] = max(dp[v][num][1], t[cur][1] - 1LL * num * num);
    zip[v][num][1] = vec[cur][1];
  }
}
void get(int v, int num, int ok, int u) {
  {
    ans[v] = num;
    for (int i = 0; i < zip[v][num][ok].size(); i++) {
      pair<int, pair<int, int> > pp = zip[v][num][ok][i];
      get(pp.first, pp.second.first, pp.second.second, v);
    }
  }
}
int main() {
  cin >> t;
  for (int q = 0; q < t; q++) {
    bool en = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++) edge[i].clear();
    init(n);
    for (int i = 0; i < m; i++) {
      int a, b;
      cin >> a >> b;
      a--;
      b--;
      edge[a].push_back(b);
      edge[b].push_back(a);
      unite(a, b);
    }
    for (int i = 0; i < n; i++) cnt[i] = cnte[i] = 0;
    for (int i = 0; i < n; i++) {
      int c = find(i);
      cnt[c] += 2;
      for (int j = 0; j < edge[i].size(); j++) {
        cnte[c]++;
      }
    }
    for (int i = 0; i < n; i++) {
      if (cnt[i] && cnte[i] >= cnt[i]) {
        puts("YES");
        for (int j = 0; j < n; j++) {
          if (find(j) == i) {
            printf("1 ");
          } else {
            printf("0 ");
          }
        }
        puts("");
        en = 1;
        break;
      }
    }
    if (en) continue;
    for (int i = 0; i < n; i++) connect[i] = 0;
    for (int i = 0; i < n; i++) {
      if (edge[i].size() >= 4) {
        puts("YES");
        for (int j = 0; j < edge[i].size(); j++) connect[edge[i][j]] = 1;
        for (int j = 0; j < n; j++) {
          if (j == i) {
            printf("2 ");
          } else if (connect[j]) {
            printf("1 ");
          } else {
            printf("0 ");
          }
        }
        puts("");
        en = 1;
        break;
      }
    }
    if (en) continue;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < 11; j++)
        for (int k = 0; k < 2; k++) dp[i][j][k] = -1e18;
    for (int i = 0; i < n; i++) ans[i] = 0;
    for (int i = 0; i < n; i++) {
      if (find(i) != i) continue;
      dfs(i, -1);
      for (int j = 0; j < 11; j++) {
        if (dp[i][j][1] >= 0) {
          puts("YES");
          get(i, j, 1, -1);
          for (int i = 0; i < n; i++) printf("%d ", ans[i]);
          puts("");
          en = 1;
          break;
        }
      }
      if (en) break;
    }
    if (en) continue;
    puts("NO");
  }
}
