#include<iostream>
#include<cstdio>
#define maxn 300005
#define maxm 600005
using namespace std;
int T,n,m,x[maxm],y[maxm],f[maxn],deg[maxn],pos; bool vis[maxm],rt[maxn];
struct{int to,nex;}a[maxn]; int head[maxn],cnt=0;
void add(int from,int to){a[++cnt].to=to; a[cnt].nex=head[from]; head[from]=cnt;}
int getfa(int p){if(f[p]==p) return p; int res=getfa(f[p]); if(res!=pos) return f[p]=res; else return res; }
void dfs(int p,int fat){
	for(int i=head[p];i;i=a[i].nex) if(a[i].to!=fat)
		{if(p!=pos){int r1=getfa(p),r2=getfa(a[i].to); f[r2]=r1;}else rt[a[i].to]=1; dfs(a[i].to,p);}
}
int main(){
	scanf("%d",&T); while(T--){
		scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) head[i]=deg[i]=0,f[i]=i; cnt=0;
		for(int i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]),vis[i]=0;
		for(int i=1;i<=m;i++){
			int r1=getfa(x[i]),r2=getfa(y[i]); if(r1==r2) continue;
			f[r2]=r1; add(x[i],y[i]); add(y[i],x[i]); vis[i]=1; deg[x[i]]++; deg[y[i]]++;
		}
		pos=-1; for(int i=1;i<=n;i++){
			if(deg[i]>n/2){pos=i; break;}
			if(i==n){printf("Yes\n"); for(int i=1;i<=m;i++) if(vis[i]) printf("%d %d\n",x[i],y[i]);}
		} if(pos==-1) continue; for(int i=1;i<=n;i++) f[i]=i; dfs(pos,-1);
		for(int i=1;i<=m;i++) if(!vis[i]){
			int r1=getfa(x[i]),r2=getfa(y[i]); if(r1!=r2&&r1!=pos&&r2!=pos){
				deg[pos]--; deg[r1]--; deg[x[i]]++; deg[y[i]]++;
				if(deg[x[i]]>n/2||deg[y[i]]>n/2){
					deg[r1]++; deg[r2]--;
					if(deg[x[i]]>n/2||deg[y[i]]>n/2){deg[pos]++; deg[r2]++; deg[x[i]]--; deg[y[i]]--; continue;}
					f[r2]=r1; vis[i]=1; rt[r2]=0; continue;
				}
				f[r1]=r2; vis[i]=1; rt[r1]=0;
			}
		} if(deg[pos]>n/2){printf("No\n"); continue;} printf("Yes\n"); int cnt=0;
		for(int i=1;i<=m&&cnt<n;i++) if(vis[i]&&!((x[i]==pos&&!rt[y[i]])||(y[i]==pos&&!rt[x[i]])))
			printf("%d %d\n",x[i],y[i]),cnt++;
	} return 0;
}