#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct edge {
	int to;
	edge *nex;
}*head[N];
void add(int u,int v) {
	edge *cur=new edge;
	cur->to=v;
	cur->nex=head[u];
	head[u]=cur;
}
int f[N];
int find(int x) {
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void uni(int x,int y) {
	f[find(x)]=find(y);
}
bool check(int x,int y) {
	return find(x)==find(y);
}
int in[N];
set<pair<int,int>> e;
vector<pair<int,int>> ee;
pair<int,int> mp(int x,int y) {
	if(x>y) swap(x,y);
	return make_pair(x,y);
}
int get() {
	e.clear(); ee.clear();
	int n,m,i,r=0,u,v;
	cin>>n>>m;
	for(i=1;i<=n;i++) head[i]=0,f[i]=i,in[i]=0;
	for(i=1;i<=m;i++) {
		cin>>u>>v;
		if(u==v) continue;
		if(u>v) swap(u,v); 
		ee.push_back({u,v});
		add(u,v),add(v,u);
		if(!check(u,v)) {
			in[u]++,in[v]++,uni(u,v);
			e.insert({u,v});
		}
	}
	for(i=1;i<=n;i++) if(in[i]>n/2) r=i;
	if(!r) {
		cout<<"Yes\n";
		for(auto x:e) {
			tie(u,v)=x;
			cout<<u<<" "<<v<<endl; 
		}
		return 0;
	}
	for(auto x:ee) {
		tie(u,v)=x;
		if(u!=r&&v!=r&&e.find(x)==e.end()) {
			if(e.find(mp(u,r))!=e.end() && e.find(mp(v,r))!=e.end()) {
				if(in[u]<in[v]) swap(u,v);
				if(in[v]+1>n/2) continue;
				e.erase(mp(u,r)); in[u]--,in[r]--;
				e.insert(mp(u,v)); in[u]++,in[v]++;
			}
		}
	}
	if(in[r]>n/2) cout<<"No\n";
	else {
		cout<<"Yes\n";
		for(auto x:e) {
			tie(u,v)=x;
			cout<<u<<" "<<v<<endl; 
		}
		return 0;
	}
	return 0;
}
int main() {
	// freopen("2.cpp","r",stdin);
	int T; cin>>T;
	while(T--) get();
	return 0;
}