#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define int long long
using namespace std;
typedef long long ll;
const int N=2e5+5,M=6,S=(1<<18)+5,inf=(ll)1e18+7,mo=998244353;
const double eps=1e-8;
void read(int &p){
	int x=0,w=1;
	char ch=0;
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
int T;
int n,m;
vector<pii>e[N];
bool ont[N];
int bel[N];
pii eg[N];
struct bcj{
    int fa[N];
    void init(){
        rep(i,1,n)
            fa[i]=i;
    }
    int find(int x){
        if(x==fa[x])return x;
        return fa[x]=find(fa[x]);
    }
    void merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return;
        fa[x]=y;
    }
}B;
int deg[N];
bool vis[N];
void dfs1(int x,int f){
    vis[x]=1;
    for(auto j:e[x]){
        if(vis[j.fir])continue;
        ont[j.sec]=1,deg[x]++,deg[j.fir]++;
        dfs1(j.fir,x);
    }
}
void print(){
    puts("Yes");
    rep(i,1,m)
        if(ont[i])printf("%lld %lld\n",eg[i].fir,eg[i].sec);
}
void dfs2(int x,int f,int bp){
    bel[x]=bp;
    for(auto j:e[x]){
        if(!ont[j.sec])continue;
        if(j.fir==f)continue;
        dfs2(j.fir,x,bp);
    }
}
int eid[N];
void solve(){
    read(n),read(m);
    rep(i,1,n)
        e[i].clear(),deg[i]=0,vis[i]=0;
    rep(i,1,m){
        int x,y;
        read(x),read(y),ont[i]=0;
        e[x].push_back(mp(y,i)),e[y].push_back(mp(x,i)),eg[i]=mp(x,y);
    }
    dfs1(1,0);
    int rt=max_element(deg+1,deg+n+1)-deg;
    if(deg[rt]<=n/2){
        print();
        return;
    }
    B.init();
    for(auto j:e[rt]){
        if(!ont[j.sec])continue;
        dfs2(j.fir,rt,j.fir),eid[j.fir]=j.sec;
    }
    rep(i,1,n){
        if(i==rt)continue;
        B.merge(i,bel[i]);
    }
    rep(i,1,m){
        if(eg[i].fir==rt||eg[i].sec==rt)continue;
        if(ont[i])continue;
        int x=B.find(eg[i].fir),y=B.find(eg[i].sec);
        if(x==y)continue;
        if(deg[x]<deg[y])swap(x,y);
        deg[x]--;
        if(deg[eg[i].fir]+1>n/2||deg[eg[i].sec]+1>n/2){
            deg[x]++;
            continue;
        }
        deg[eg[i].fir]++,deg[eg[i].sec]++,deg[rt]--;
        ont[i]=1,ont[eid[x]]=0,B.merge(x,y);
    }
    if(deg[rt]>n/2)puts("No");
    else print();
}
signed main(){
    read(T);
    while(T--)
        solve();
    return 0;
}