#include<bits/stdc++.h> 
#define ll long long 
#define x first 
#define y second 
#define il inline 
#define em emplace 
#define eb emplace_back 
#define debug() puts("-----") 
using namespace std; 
typedef pair<int,int> pii; 
il int read(){ 
	int x=0,f=1; char ch=getchar(); 
	while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } 
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 
	return x*f; 
} 
const int N=1e5+10,M=2e5+10; 
int n,m; 
int p[N]; 
int d[N]; 
pii E[N]; 
int fa[N]; 
il int find(int x){
	if(p[x]!=x) p[x]=find(p[x]); 
	return p[x]; 
} bool st[N]; 
il int Find(int x){ 
	if(!fa[x]) return 0; 
	if(fa[x]!=x) fa[x]=Find(fa[x]);
	return fa[x]; 
} 
vector<int> e[N]; 
il void dfs(int u,int fat,int Fa){ 
	fa[u]=Fa; 
	for(auto to:e[u]) if(to!=fat) dfs(to,u,Fa);  
} 
int id[N]; 
il void solve(){ 
	n=read(),m=read(); 
	for(int i=1;i<=n;i++) p[i]=i,d[i]=0,fa[i]=0,e[i].clear(),id[i]=0; 
	for(int i=1;i<=m;i++){ 
		st[i]=false; 
		E[i].x=read(),E[i].y=read(); 
		int pa=find(E[i].x),pb=find(E[i].y); 
		if(pa!=pb) p[pa]=pb,d[E[i].x]++,d[E[i].y]++,st[i]=true,e[E[i].x].eb(E[i].y),e[E[i].y].eb(E[i].x); 
	} int rt=0; 
	for(int i=1;i<=n;i++) if(d[i]>d[rt]) rt=i; 
	if(d[rt]>n/2){ 
		vector<int> son; 
		for(int i=1;i<=m;i++){ 
			if(!st[i]) continue; 
			if(E[i].x==rt) son.eb(E[i].y),id[E[i].y]=i; 
			if(E[i].y==rt) son.eb(E[i].x),id[E[i].x]=i; 
		} for(auto u:son) dfs(u,0,u); 
		for(int i=1;i<=m;i++){ 
			if(st[i]) continue; 
			if(E[i].x==rt||E[i].y==rt) continue; 
			int pa=Find(E[i].x),pb=Find(E[i].y); 
			if(pa!=pb){ 
				if(d[pa]>d[pb]) swap(pa,pb),swap(E[i].x,E[i].y); 
				d[rt]--,d[pb]--,d[E[i].x]++,d[E[i].y]++; 
				st[i]=true,st[id[pb]]=false; fa[pb]=pa; 
			} if(d[rt]<=n/2) break; 
		} if(d[rt]>n/2){ puts("No"); return ; } 
	} puts("Yes"); 
	for(int i=1;i<=m;i++) if(st[i]) cout<<E[i].x<<" "<<E[i].y<<endl; 
} 
signed main(){ 
	int T=read();
	while(T--) solve(); 
	return 0; 
}  /*
2
6 9
1 2
1 3
1 4
2 3
2 4
3 4
4 5
4 6
4 6
3 4
1 3
2 3
3 3
1 2
*/