#include <bits/stdc++.h>
 
using namespace std;
 
const int MaxN = 1e3 + 10;
 
const int L = 2018; //Happy New Year!!! :)
const int LL = L * L; 
 
int n, m, f[MaxN], l, lo, hi;
int g[MaxN][MaxN], deg[MaxN];
bitset < MaxN > bit[MaxN];
int u[MaxN];
 
bool cmp(int x, int y) {
	return deg[x] > deg[y];
}
 
void solve() {
	scanf("%d%d", &n, &m);
	assert (2 <= n && n <= 1000);
	assert (1 <= m && m <= 1000000);
	memset(g, 0, sizeof(g));
	memset(f, -1, sizeof(f));
	memset(u, 0, sizeof(u));
	memset(deg, 0, sizeof(deg));
	for (int i = 1; i <= n; ++i) {
		bit[i].reset();
	}
	lo = 0;
	hi = L;
	for (int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		assert (u != v && !bit[u].test(v));
		bit[u].set(v, true);
		bit[v].set(u, true);
		g[u][v] = g[v][u] = 1;
		deg[u] += 1;
		deg[v] += 1;
	}
	int b = 0;
	for (int i = 1; i <= n; ++i) {
		if (deg[i] > deg[b]) {
			b = i;
		}
	}
	int e = 0;
	for (int i = 1; i <= n; ++i) {
		if (g[b][i] == 1 && deg[i] > deg[e]) {
			e = i;
		}
	}
	int cnt = (bit[b] & bit[e]).count();
	if (cnt > 1) {
		printf("No\n");
		return;
	}
	if (cnt == 1) {
		int l2 = 0;
		for (int i = 1; i <= n; ++i) {
			if (g[b][i] && g[e][i]) {
				l2 = i;
			}
		}
		if (deg[l2] != 2) {
			printf("No\n");
			return;
		}
		bool ok = true;
		vector < int > A, B;
		for (int i = 1; i <= n; ++i) {
			if (i == l2) {
				u[i] = 3;
			} else if (g[b][i] == 1) {
				u[i] = 2;
				ok &= g[e][i] == 0;
				B.push_back(i);
			} else {
				u[i] = 1;
				ok &= g[b][i] == 0;
				A.push_back(i);
			}
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (g[i][j] == 1) {
					ok &= u[i] != u[j];
				}
			}
		}
		if (!ok) {
			printf("No\n");
			return;
		}
		assert ((int)A.size() + (int)B.size() + 1 == n);
		sort(A.begin(), A.end(), cmp);
		sort(B.begin(), B.end(), cmp);
		if (deg[b] != deg[A[0]] || deg[e] != deg[B[0]]) {
			printf("No\n");
			return;
		}
		for (int i = 0; i + 1 < (int)A.size(); ++i) {
			ok &= ((bit[A[i]] & bit[A[i + 1]]) == bit[A[i + 1]]);
		}
		for (int i = 0; i + 1 < (int)B.size(); ++i) {
			ok &= ((bit[B[i]] & bit[B[i + 1]]) == bit[B[i + 1]]);
		}
		if (!ok) {
			printf("No\n");
			return;
		}
		
		f[b] = 0;
		f[l2] = LL / 2;
		f[e] = LL;
		
		for (int i = 1; i < (int)A.size(); ++i) {
			f[A[i]] = i * L;
		}
		for (int i = 1, ptr = (int)A.size() - 1; i < (int)B.size(); ++i) {
			if (i == 0) {
				while (ptr >= 0 && !g[A[ptr]][B[i]]) {
					ptr--;
				}
				f[B[i]] = f[A[ptr]] + LL / 2 + L - 1;
			} else {
				while (ptr >= 0 && !g[A[ptr]][B[i]]) {
					ptr--;
				}
				f[B[i]] = f[B[i - 1]] - 1;
				while (f[B[i]] - f[A[ptr]] - L >= LL / 2) {
					f[B[i]] -= L;
				}				
			}
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = i + 1; j <= n; ++j) {
				ok &= (g[i][j] == (abs(f[i] - f[j]) >= LL / 2));
			}
		}
		if (!ok) {
			printf("No\n");
			return;
		}
		printf("Yes\n");
		printf("%d ", LL);
		for (int i = 1; i <= n; ++i) {
			printf("%d%c", f[i], i == n ? '\n' : ' ');
		}
	} else {
		bool ok = true;
		vector < int > A, B;
		for (int i = 1; i <= n; ++i) {
			if (g[b][i] == 1) {
				u[i] = 2;
				ok &= g[e][i] == 0;
				B.push_back(i);
			} else {
				ok &= g[b][i] == 0;
				u[i] = 1;
				A.push_back(i);
			}
		}
//		cout << b << ' ' << e << ' ' << ok << '\n';
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (g[i][j] == 1) {
					ok &= u[i] != u[j];
				}
			}
		}
		if (!ok) {
			printf("No\n");
			return;
		}
		assert ((int)A.size() + (int)B.size() == n);
		sort(A.begin(), A.end(), cmp);
		sort(B.begin(), B.end(), cmp);
		for (int i = 0; i + 1 < (int)A.size(); ++i) {
			ok &= ((bit[A[i]] & bit[A[i + 1]]) == bit[A[i + 1]]);
		}
		for (int i = 0; i + 1 < (int)B.size(); ++i) {
			ok &= ((bit[B[i]] & bit[B[i + 1]]) == bit[B[i + 1]]);
		}
		if (!ok) {
			printf("No\n");
			return;
		}
/*		for (int i = 0; i < (int)A.size(); ++i) {
			cout << A[i] << ' ';
		}
		cout << '\n';
		for (int i = 0; i < (int)B.size(); ++i) {
			cout << B[i] << ' ';
		}
		cout << '\n';
		*/
		for (int i = 0; i < (int)A.size(); ++i) {
			f[A[i]] = i * L;
		}
		for (int i = 0, ptr = (int)A.size() - 1; i < (int)B.size(); ++i) {
			if (i == 0) {
				while (ptr >= 0 && !g[A[ptr]][B[i]]) {
					ptr--;
				}
				f[B[i]] = f[A[ptr]] + LL / 2 + L - 1;
			} else {
				while (ptr >= 0 && !g[A[ptr]][B[i]]) {
					ptr--;
				}
				f[B[i]] = f[B[i - 1]] - 1;
				while (f[B[i]] - f[A[ptr]] - L >= LL / 2) {
					f[B[i]] -= L;
				}				
			}
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = i + 1; j <= n; ++j) {
				ok &= (g[i][j] == (abs(f[i] - f[j]) >= LL / 2));
			}
		}
		if (!ok) {
			printf("No\n");
			return;
		}
		printf("Yes\n");
		printf("%d ", LL);
		for (int i = 1; i <= n; ++i) {
			printf("%d%c", f[i], i == n ? '\n' : ' ');
		}
	}
}
 
int main() {
//	freopen("input.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	assert (1 <= t && t <= 5);
	while (t --> 0) {
		solve();
	}
 
	return 0;
}