#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n,m,dfn[N],fa[N],low[N],il[N],du[N],gl,Fa;
int Case;
bool dl[N];
vector<int>e[N],g[N];
void tarjan(int x){
	dfn[x]=++dfn[0],low[x]=il[x]=x;
	for(auto v:e[x]){
		if(!dfn[v]){
			++du[x],++du[v];
			g[x].push_back(v),fa[v]=x;
			tarjan(v);
			if(dfn[low[v]]<dfn[low[x]])low[x]=low[v],il[x]=il[v];
		}else if(dfn[v]<dfn[low[x]])il[x]=x,low[x]=v;
	}
	if(du[x]>n/2)gl=x;
}
void solve(){
	++Case;
	scanf("%d%d",&n,&m);
	if(Case==120)printf("%d %d\n",n,m);
	gl=dfn[0]=Fa=0;
	for(int i=1;i<=n;++i)e[i].clear(),g[i].clear(),dfn[i]=low[i]=il[i]=fa[i]=du[i]=dl[i]=0;
	for(int i=1,x,y;i<=m;++i){
		scanf("%d%d",&x,&y);if(Case==120)printf("%d %d\n",x,y);
		e[x].push_back(y),e[y].push_back(x);
	}if(T>1000)return;
	tarjan(1);
	if(gl){
		bool fg=false;
		int ct=0;
		for(auto v:g[gl]){
			if(dfn[low[v]]<dfn[gl]){
				++ct;
				if(low[v]!=fa[gl])fg=true;
			}
		}
		if(du[gl]-ct>n/2||!fg&&(du[fa[gl]]+du[gl]-n/2>n/2)){
			if(du[gl]-ct<=n/2){
				for(auto v:e[gl])if(dfn[v]<dfn[fa[gl]]){
					dl[gl]=true;
					Fa=v;
					break;
				}
				if(!Fa)return puts("No"),void();
			}else return puts("No"),void();
		}
	}
	puts("Yes");
	if(Fa)printf("%d %d\n",Fa,gl);
	for(auto v:g[gl])if(du[gl]>n/2&&dfn[low[v]]<dfn[fa[gl]]){
		dl[v]=true;
		printf("%d %d\n",low[v],il[v]);
		--du[gl];
	}
	for(auto v:g[gl])if(du[gl]>n/2&&low[v]==fa[gl]){
		dl[v]=true;
		printf("%d %d\n",low[v],il[v]);
		--du[gl];
	}
	for(int i=1;i<=n;++i)for(auto v:g[i])if(!dl[v])printf("%d %d\n",i,v);
}
int main(){
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}