/*
	Luogu name: Symbolize
	Luogu uid: 672793
*/
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define rep1(i,l,r) for(register int i=l;i<=r;++i)
#define rep2(i,l,r) for(register int i=l;i>=r;--i)
#define rep3(i,x,y,z) for(register int i=x[y];~i;i=z[i])
#define rep4(i,x) for(auto i:x)
#define debug() puts("----------")
const int N=5e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
using namespace std;
int t,n,m,fa[N],f[N],times[N],dep[N];
bool vis[N];
vector<pii> G[N];
struct Graph{int u,v;}e[N];
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 f*x;
}
int find(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void dfs(int x,int Fa,int top)
{
	dep[x]=dep[Fa]+1;
	fa[x]=top;
	rep4(to,G[x])
	{
		if(to.x==Fa) continue;
		dfs(to.x,x,top);
	}
	return;
}
void getans()
{
	n=read();
	m=read();
	rep1(i,1,n) 
	{
		G[i].clear();
		fa[i]=i;
		times[i]=0;
	}
	rep1(i,1,m) vis[i]=0;
	int cnt=0;
	rep1(i,1,m)
	{
		e[i].u=read();
		e[i].v=read();
		int x=find(e[i].u),y=find(e[i].v);
		if(x==y) continue;
		G[x].push_back(make_pair(y,i));
		G[y].push_back(make_pair(x,i));
		fa[x]=y;
		vis[i]=1;
		++cnt;
		++times[e[i].u];
		++times[e[i].v];
	}
	if(n==3)
	{
		puts("No");
		return;
	}
	int rt=0; 
	rep1(i,1,n) if(times[i]>n/2) rt=i;
	fa[rt]=rt;
	rep4(to,G[rt])
	{
		f[to.x]=to.y;
		dfs(to.x,rt,to.x);
	}
	rep1(i,1,m)
	{
		if(times[rt]<=n/2) break;
		int x=find(e[i].u),y=find(e[i].v);
		if(x==y||x==rt||y==rt) continue;
		if(dep[e[i].u]>dep[e[i].v]) swap(e[i].u,e[i].v),swap(x,y);
		if(dep[e[i].u]==1&&times[e[i].u]<times[e[i].v]) swap(e[i].u,e[i].v),swap(x,y);
		fa[x]=y;
		vis[f[x]]=0;
		assert(f[x]>=1&&f[x]<=m);
		vis[i]=1;
		--times[x];
		--times[rt];
		++times[e[i].u];
		++times[e[i].v];
	}
	if(times[rt]>n/2) puts("No");
	else
	{
//		rep1(i,1,n) 
//		{
//			if(times[i]>n/2)
//			{
//				debug();
//				cout<<n<<' '<<m<<"\n";
//				rep1(j,1,m) cout<<e[j].u<<' '<<e[j].v<<"\n";
//			}
//		}
		puts("Yes");
		rep1(i,1,m) if(vis[i]) cout<<e[i].u<<' '<<e[i].v<<"\n";
	}
	return;
}
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	t=read();
	while(t--) getans();
	return 0;
}
/*
1
3 4
1 3
2 3
3 3
1 2
*/