// Code by Heratino & Nelofus
// Narcissus & どうか安寧な記憶を

#include <bits/stdc++.h>
using i64 = long long;

//{{{星光闪耀
template<typename Ta, typename Tb>
inline void chkmax(Ta &a, const Tb &b) {if (a < b)	a = b;}
template<typename Ta, typename Tb>
inline void chkmin(Ta &a, const Tb &b) {if (a > b)	a = b;}
char buf[1 << 20], *P1, *P2;
inline char gc() {
	if (P1 == P2)
		P2 = (P1 = buf) + fread(buf, 1, 1 << 20, stdin);
	return P1 == P2 ? EOF : *P1++;
}
template<typename T>
inline void read(T &ans) {
	ans = 0;
	T w = 1;
	char c = gc();
	while (!isdigit(c)) {
		if (c == '-')	w = -1;
		c = gc();
	}
	while (isdigit(c)) {
		ans = (ans << 3) + (ans << 1) + (c ^ 48);
		c = gc();
	}
	ans *= w;
}
template<typename T, typename ...Ts>
void read(T &a, Ts&... other) {
	read(a);
	read(other...);
}
//}}}

constexpr int N = 2e5 + 10;

std::pair<int, int> E[N];
bool isAnswer[N];
int deg[N];
std::vector<int> G[N];
int n, m;

inline int get(int u, int x) {return u ^ E[x].first ^ E[x].second;}

struct DSU_ {
	int fa[N], siz[N];
	void init(int _n) {
		for (int i = 1; i <= _n; i++)
			fa[i] = i, siz[i] = 1;
	}
	inline int find(int x) {
		return x == fa[x] ? x : fa[x] = find(fa[x]);
	}
	inline bool merge(int u, int v) {
		u = find(u), v = find(v);
		if (u == v)
			return false;
		if (siz[u] < siz[v])
			siz[v] += siz[u], fa[u] = v;
		else
			siz[u] += siz[v], fa[v] = u;
		return true;
	}
} DSU;

int tot = 0;

void clear() {
	tot = 0;
	DSU.init(n);
	memset(isAnswer + 1, 0, m * sizeof(bool));
	memset(deg + 1, 0, n * sizeof(int));
	for (int i = 1; i <= n; i++)
		G[i].clear();
}

void dfs(int u, int fa) {
	for (const int &i : G[u]) {
		int v = get(u, i);
		if (v == fa)
			continue;
		DSU.fa[v] = DSU.fa[u];
		dfs(v, u);
	}
}

void solve() {
	read(n, m);
	clear();

	for (int i = 1; i <= m; i++) {
		int u, v;
		read(u, v);
		if (u == v)
			continue;
		if (u > v)
			std::swap(u, v);
		E[++tot] = std::make_pair(u, v);
	}

	std::sort(E + 1, E + 1 + tot);
	m = std::unique(E + 1, E + 1 + tot) - E - 1;

	for (int i = 1; i <= m; i++) {
		const auto &[u, v] = E[i];
		if (DSU.merge(u, v)) {
			G[u].push_back(i);
			G[v].push_back(i);
			isAnswer[i] = true;
			deg[u]++, deg[v]++;
		}
	}
	int rt = 0;
	for (int i = 1; i <= n; i++)
		if (deg[i] > n / 2)
			rt = i;
	if (!rt) {
		std::cout << "Yes\n";
		for (int i = 1; i <= m; i++) {
			const auto &[u, v] = E[i];
			if (isAnswer[i])
				std::cout << u << ' ' << v << '\n';
		}
		return ;
	}

	DSU.init(n);
	for (const int &i : G[rt]) {
		dfs(get(rt, i), rt);
	}
	for (int i = 1; i <= m; i++) {
		if (isAnswer[i]) {
			continue;
		}
		auto [u, v] = E[i];
		if (u == rt || v == rt || DSU.find(u) == DSU.find(v))
			continue;
		int sonu = DSU.find(u);
		int sonv = DSU.find(v);
		deg[rt]--, deg[u]++, deg[v]++, deg[sonu]--;
		if (deg[u] > n / 2 || deg[v] > n / 2) {
			std::swap(u, v);
			std::swap(sonu, sonv);
			deg[sonu]--, deg[sonv]++;
		}
		if (deg[u] > n / 2 || deg[v] > n / 2) {
			deg[u]--, deg[v]--, deg[sonu]++, deg[rt]++;
			continue;
		}
		DSU.fa[sonu] = DSU.fa[sonv];
		isAnswer[i] = true;
		auto pr = std::make_pair(std::min(rt, sonu), std::max(rt, sonu));
		int t = std::lower_bound(E + 1, E + 1 + m, pr) - E;

		assert(E[t] == pr);

		isAnswer[t] = false;
		if (deg[rt] <= n / 2)
			break;
	}
	if (deg[rt] <= n / 2) {
		std::cout << "Yes\n";
		for (int i = 1; i <= m; i++) {
			if (isAnswer[i])
				std::cout << E[i].first << ' ' << E[i].second << '\n';
		}
	} else {
		std::cout << "No\n";
	}
}

int main() {
#ifdef HeratinoNelofus
	freopen("input.txt", "r", stdin);
#endif

	int T;
	read(T);
	while (T--) {
		solve();
	}
	return 0;
}