#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;
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(){
	scanf("%d%d",&n,&m);
	gl=dfn[0]=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);
		e[x].push_back(y),e[y].push_back(x);
	}
	if(n==3)return puts("No"),void();
	tarjan(1);
	if(gl){
		int ct=0;
		for(auto v:g[gl])if(dfn[low[v]]<dfn[gl])++ct;
		if(du[gl]-ct>n/2)return puts("No"),void();
	}
	puts("Yes");
	for(auto v:g[gl])if(du[gl]>n/2&&dfn[low[v]]<dfn[gl]){
		if(!dl[gl]&&du[il[v]]<n/2)dl[gl]=true;
		else 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;
}