#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=1e5+10;
int T,n,m;
vector<pair<int,int> >E,S,P,ans,res;
int fa[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool merge(int x,int y){
	x=find(x),y=find(y);
	if(x==y)return 0;
	return fa[x]=y,1;
}
int deg[N];
void get(){
	E.clear(),S.clear(),P.clear(),ans.clear(),res.clear();
	scanf("%d%d",&n,&m);
	iota(fa,fa+1+n,0);
	fill(deg+1,deg+1+n,0);
	for(int u,v;m--;){
		scanf("%d%d",&u,&v);
		if(u==v)continue;
		P.push_back({u,v});
		if(!merge(u,v))E.push_back({u,v});
		else S.push_back({u,v}),deg[u]++,deg[v]++;
	}
	if(n==3){
		puts("No");return;
	}
	int rt=max_element(deg+1,deg+1+n)-deg;
	iota(fa,fa+1+n,0);
	for(auto e:S)if(e.first!=rt&&e.second!=rt){
		merge(e.first,e.second);
	}
	for(auto e:E)if(e.first!=rt&&e.second!=rt){
		if(deg[rt]*2<=n)break;
		if(merge(e.first,e.second))ans.push_back(e),deg[rt]--;
	}
	if(deg[rt]*2>n){
		puts("No");return;
	}
	iota(fa,fa+1+n,0);
	for(auto e:ans)merge(e.first,e.second);
	for(auto e:S)if(e.first!=rt&&e.second!=rt){
		if(merge(e.first,e.second))ans.push_back(e);
	}
	for(auto e:S){
		if(merge(e.first,e.second))ans.push_back(e);
	}
	fill(deg+1,deg+1+n,0);
	for(auto e:ans)deg[e.first]++,deg[e.second]++;
	rt=max_element(deg+1,deg+1+n)-deg;
	if(deg[rt]*2<=n){
		puts("Yes");
		for(auto e:ans)printf("%d %d\n",e.first,e.second);
	}else{
		int u=0,v=0;
		iota(fa,fa+1+n,0);
		for(auto e:ans)if(e.first!=rt&&e.second!=rt){
			merge(e.first,e.second);
		}
		for(auto e:ans)debug(e.first,e.second);
		for(auto e:P)if(deg[e.first]*2<=n&&deg[e.second]*2<=n&&merge(e.first,e.second)){
			tie(u,v)=e;break;
		}
		debug(u,v);
		if(!u){
			puts("No");
		}else{
			iota(fa,fa+1+n,0);
			merge(u,v);
			res.push_back({u,v});
			for(auto e:ans)if(deg[e.first]*2+1<n&&deg[e.second]*2+1<n){
				if(merge(e.first,e.second))res.push_back(e);
			}
			for(auto e:ans)if(deg[e.first]*2<=n&&deg[e.second]*2<=n){
				if(merge(e.first,e.second))res.push_back(e);
			}
			for(auto e:ans){
				if(merge(e.first,e.second))res.push_back(e);
			}
			assert(res.size()==n-1);
			puts("Yes");
			for(auto e:res)printf("%d %d\n",e.first,e.second);
		}
	}
}
int main(){
	for(scanf("%d",&T);T--;)get();
	return 0;
}