#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+15;
int in[N];
struct edge {
	int to;
	edge *nex;
}*head[N];
int vis[N];
int f[N];
vector<pair<int,int>> e;
vector<pair<int,int>> d;
int find(int x) {
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void uni(int x,int y) {
	if(vis[find(x)]) swap(x,y);
	f[find(x)]=find(y);
}
bool check(int x,int y) {
	return find(x)==find(y);
}
void add(int u,int v) {
	edge *cur=new edge;
	cur->to=v;
	cur->nex=head[u];
	head[u]=cur;
}
int T,cnt;
void get() {
	e.clear();
	d.clear();
	int n,m,u,v,i,j;
	cnt++;
	cin>>n>>m; if(cnt==127) cout<<n<<" "<<m<<endl;
	for(i=1;i<=n;i++) in[i]=vis[i]=0,head[i]=0,f[i]=i;
	for(i=1;i<=m;i++) {
		cin>>u>>v; if(cnt==127) cout<<u<<" "<<v<<endl;
		if(!check(u,v)) {
			uni(u,v);
			in[u]++;
			in[v]++;
			add(u,v);
			add(v,u);
			d.emplace_back(u,v);
		} else {
			e.emplace_back(u,v);
		}
	}
	if(T>5) return ;
	int r=0;
	for(i=1;i<=n;i++) if(in[i]>n/2) r=i;
	if(!r) {
		cout<<"Yes\n";
		for(auto x:d) {
			tie(u,v)=x;
			cout<<u<<" "<<v<<endl;
		}
		return ;
	}
	for(i=1;i<=n;i++) f[i]=i;
	for(auto x:d) {
		tie(u,v)=x;
		if(u==r) vis[v]=1;
		else if(v==r) vis[u]=1;
		else uni(u,v);
		// cout<<"pre in"<<u<<" "<<v<<endl;
	}
	for(auto x:d) {
		tie(u,v)=x;
		if(u==r) ;
		else if(v==r) ;
		else uni(u,v);
	}
	for(auto x:e) {
		tie(u,v)=x;
		if(u!=r&&v!=r&&!check(u,v)) {
			
			in[u]++,in[v]++;
			i=find(u),j=find(v);
			if(in[i]<in[j]) swap(i,j);
			in[i]--,in[r]--;
			
			if(in[u]>n/2||in[v]>n/2) {
				in[u]--,in[v]--;
				in[r]++,in[i]++;
				continue;
			}
			
			if(vis[i]==0) {
				cout<<u<<" "<<v<<endl;
				cout<<i<<" "<<j<<endl; 
				cout<<vis[i]<<" "<<vis[j]<<endl;
			}
			
			//assert(vis[i]);
			//assert(vis[j]);
			vis[i]=0; uni(i,j);
			d.emplace_back(u,v);
		}
	}
	if(in[r]>n/2) {
		cout<<"No\n";
	} else {
		cout<<"Yes\n";
		for(auto x:d) {
			tie(u,v)=x;
			if(u==r||v==r) continue;
			cout<<u<<" "<<v<<endl;
		}
		for(i=1;i<=n;i++) if(vis[i]) cout<<r<<" "<<i<<endl;
		return ;
	}
}
int main() {
	cin>>T;
	while(T--) get();
	return 0;
}