#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define lowbit(x) (x&-x)
#define inf 2000000000
#define log(x) (31^__builtin_clz(x))
using namespace std;
int f[200005],vis[200005],siz[200005],nsiz[200005];
int find(int x){
	return f[x]==x?x:find(f[x]);
}
vector<int>e[200005];
map<int,int>mp[200005];
vector<pii>ans,ed;
void dfs1(int x){
	vis[x]=1;
	for(auto u:e[x]){
		if(vis[u])continue;
		ans.push_back({x,u});
		dfs1(u);
	}
}
int n,m;
void con(int u,int v){
	if(find(u)!=find(v)&&nsiz[u]<n/2&&nsiz[v]<n/2){
		ans.push_back({u,v});
		f[max(find(u),find(v))]=min(find(u),find(v));
		nsiz[u]++;
		nsiz[v]++;
	}
}
int snow=0,p=0;
void solve(){
	cin>>n>>m;
	snow++;
	ans.clear();
	ed.clear();
	for(int i=1;i<=n;i++){
		e[i].clear();
		vis[i]=0;
		f[i]=i;
		mp[i].clear();
		siz[i]=0;
		nsiz[i]=0;
	}
	if(snow==16&&p)cout<<n<<" "<<m<<"\n";
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
	if(snow==16&&p)cout<<u<<" "<<v<<"\n";
		if(u==v||mp[u][v]){
			i--;
			m--;
			continue;
		}
		e[u].push_back(v);
		e[v].push_back(u);
		ed.push_back({u,v});
		mp[u][v]=mp[v][u]=1;
	}
	int mx=0;
	for(int i=1;i<=n;i++){
		if(e[i].size()>e[mx].size())mx=i;
	}
	if(e[mx].size()<=n/2){
		dfs1(1);
		cout<<"Yes\n";
		for(auto u:ans){
			cout<<u.first<<" "<<u.second<<"\n";
		}
		return;
	}
	for(auto u:ed){
		if(u.first==mx||u.second==mx)continue;
		int s=find(u.first),t=find(u.second);
		if(s!=t){
			f[max(s,t)]=min(s,t);
		}
	}
	int sz=0;
	for(int i=1;i<=n;i++){
		if(i==mx)continue;
		if(find(i)==i)sz++;
	}
	if(sz>n/2){
		cout<<"No\n";
		return;
	}
	for(int i=1;i<=n;i++){
		if(i==mx)continue;
		siz[find(i)]++;
		if(vis[find(i)]==0&&mp[i][mx]){
			vis[find(i)]=1;
			ans.push_back({i,mx});
			//vs[i]=1;
		}
	}
	vector<int>tot;
	int t;
	for(int i=1;i<=n;i++){
		if(siz[i]>n/2){
			for(int j=1;j<=n;j++){
				if(find(j)==i){
					tot.push_back(j);
					if(vis[j])t=j;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	for(auto u:ans){
		con(u.first,u.second);
		ans.pop_back();
	}
	for(auto u:tot){
		for(auto v:e[u]){
			if(v!=mx&&v!=t&&u!=mx&&u!=t&&!mp[u][mx]&&!mp[v][mx]){
				con(u,v);
			}
		}
	}
	for(auto u:tot){
		for(auto v:e[u]){
			if(v!=mx&&v!=t&&u!=mx&&u!=t){
				con(u,v);
			}
		}
	}
	for(auto u:tot){
		for(auto v:e[u]){
			if(v!=t&&u!=t){
				con(u,v);
			}
		}
	}
	for(auto u:e[mx])con(u,mx);
	for(auto u:ed)con(u.first,u.second);
	if(p)return;
	if(ans.size()!=n-1){
		cout<<"No\n";
		return;
	}
	cout<<"Yes\n";
	for(auto u:ans){
		cout<<u.first<<" "<<u.second<<"\n";
	}
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int t=1;
	cin>>t;
	if(t>100)p=1;
    while(t--)solve();
    return 0;
}