#include <bits/stdc++.h>
#define rep(i, d, u) for(int i = d; i <= u; ++i)
#define dep(i, u, d) for(int i = u; i >= d; --i)
#define cep(n) while(n--)
#define gep(i, a) for(int i = firs[a]; i; i = neig[i])
int ured() {
	int ch, re = 0;
	do {
		ch = getchar();
	} while('9' < ch || ch < '0');
	do {
		re = re * 10 + (ch ^ '0');
	} while('0' <= (ch = getchar()) && ch <= '9');
	return re;
}
void uwit(int da) {
	int ch[21], cn = 0;
	do {
		ch[++cn] = da - da / 10 * 10;
	} while(da /= 10);
	do {
		putchar('0' ^ ch[cn]);
	} while(--cn);
}
const int _maxn = 500011, _maxm = 1000011;
int t, n, m, u[_maxn], v[_maxn], fath[_maxn], indu[_maxn], cnts, atno, btno, ctno, ated[_maxn];
bool pdif[_maxn], pdis;
int find(int at) {
	return fath[at] == at ? at : (fath[at] = find(fath[at]));
}
int main() {
	t = ured();
	cep(t) {
		n = ured(), m = ured(), cnts = 0, atno = btno = 0;
		rep(i, 1, n) {
			fath[i] = i, indu[i] = 0;
		}
		rep(i, 1, m) {
			u[i] = ured(), v[i] = ured();
			if(find(u[i]) == find(v[i])) {
				pdif[i] = 0;
			} else {
				pdif[i] = 1, ++cnts, ++indu[u[i]], ++indu[v[i]], fath[find(u[i])] = find(v[i]);
			}
		}
		if(n == 3 || cnts < n - 1) {
			puts("No");
			continue;
		}
		rep(i, 1, n) {
			if(indu[i] << 1 > n) {
				atno = i;
				break;
			}
		}
		if(!atno) {
			puts("Yes");
			rep(i, 1, m) {
				if(pdif[i]) {
					uwit(u[i]), putchar(' '), uwit(v[i]), putchar('\n');
				}
			}
			continue;
		}
		rep(i, 1, n) {
			fath[i] = i;
		}
		rep(i, 1, m) {
			if(pdif[i] && u[i] != atno && v[i] != atno) {
				fath[find(u[i])] = find(v[i]);
			}
		}
		rep(i, 1, m) {
			if(pdif[i] && (u[i] == atno || v[i] == atno)) {
				ated[find(u[i] ^ v[i] ^ atno)] = i;
			}
		}
		rep(i, 1, m) {
			if(!pdif[i] && u[i] != v[i] && u[i] != atno && v[i] != atno) {
				pdif[ated[find(u[i])]] = 0, pdif[i] = 1, --indu[u[ated[find(u[i])]]], --indu[v[ated[find(u[i])]]];
				++indu[u[i]], ++indu[v[i]], fath[find(u[i])] = find(v[i]);
				if(indu[atno] << 1 <= n) {
					break;
				}
			}
		}
		if(indu[atno] << 1 > n) {
			puts("No");
			continue;
		}
		rep(i, 1, n) {
			if(indu[i] << 1 > n) {
				btno = i;
				break;
			}
		}
		if(!btno) {
			puts("Yes");
			rep(i, 1, m) {
				if(pdif[i]) {
					uwit(u[i]), putchar(' '), uwit(v[i]), putchar('\n');
				}
			}
			continue;
		}
		fath[atno] = fath[btno] = 0;
		rep(i, 1, m) {
			if(pdif[i]) {
				if(!fath[u[i]] && !fath[v[i]]) {
					ctno = i;
				} else if(!fath[v[i]]) {
					fath[u[i]] = v[i], ated[u[i]] = i;
				} else if(!fath[u[i]]) {
					fath[v[i]] = u[i], ated[v[i]] = i;
				}
			}
		}
		pdis = 1;
		rep(i, 1, m) {
			if(!pdif[i] && u[i] != v[i]) {
				if(fath[u[i]] && fath[v[i]]) {
					pdif[i] = 1;
					if(fath[u[i]] == fath[v[i]]) {
						pdif[ated[u[i]]] = 0;
					} else {
						pdif[ctno] = 0;
					}
					pdis = 0;
					break;
				} else if(fath[u[i]] && !fath[v[i]]) {
					if(v[i] == atno && fath[u[i]] == btno) {
						pdif[ctno] = 0, pdif[i] = 1, pdis = 0;
						break;
					}
				} else if(!fath[u[i]] && fath[v[i]]) {
					if(u[i] == atno && fath[v[i]] == btno) {
						pdif[ctno] = 0, pdif[i] = 1, pdis = 0;
						break;
					}
				}
			}
		}
		if(pdis) {
			puts("No");
		} else {
			puts("Yes");
			rep(i, 1, m) {
				if(pdif[i]) {
					uwit(u[i]), putchar(' '), uwit(v[i]), putchar('\n');
				}
			}
		}
	}
	return 0;
}