#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template <typename Type>
using vec=vector<Type>;
template <typename Type>
using grheap=priority_queue<Type>;
template <typename Type>
using lrheap=priority_queue<Type,vector<Type>,greater<Type> >;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)

const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7/*998244353*/;

const int N=1e5+5,M=2e5+5;

int n,m;
int u,v;
int rt;
int dg[N];
struct edge{
    int a,b;
}es[M];
bool use[M];
int dte[N];

struct DSU{
    int fa[N];
    void init(int n){
        rep(i,1,n)fa[i]=i;
    }
    int find(int x){
        if(fa[x]!=x)fa[x]=find(fa[x]);
        return fa[x];
    }
    void merge(int a,int b){
        a=find(a);b=find(b);
        fa[a]=b;
    }
    bool same(int a,int b){
        return find(a)==find(b);
    }
}dsu;

void outans(){
    cout<<"Yes\n";
    rep(k,1,m){
        if(use[k])cout<<es[k].a<<" "<<es[k].b<<"\n";
    }
}

vec<int> g[N];
bool vis[N];
void dfs(int now,int fa){
    vis[now]=true;
    dsu.merge(now,fa);
    for(auto nxt:g[now]){
        if(vis[nxt])continue;
        dfs(nxt,fa);
    }
}

void solve(){
    cin>>n>>m;
    rep(i,1,n)dg[i]=0;
    rep(i,1,m){
        cin>>u>>v;
        use[i]=0;
        es[i].a=u;es[i].b=v;
    }
    dsu.init(n);
    rep(i,1,n)g[i].clear();
    rep(i,1,m){
        if(!dsu.same(es[i].a,es[i].b)){
            dsu.merge(es[i].a,es[i].b);
            use[i]=1;
            dg[es[i].a]++;
            dg[es[i].b]++;
        }
    }
    rt=0;
    rep(i,1,n){
        if(dg[i]>n/2){
            rt=i;
            break;
        }
    }
    if(!rt){
        outans();
        return;
    }
    rep(i,1,m){
        if(es[i].a==rt)dte[es[i].b]=i;
        if(es[i].b==rt)dte[es[i].a]=i;
    }
    rep(i,1,m){
        if(use[i]){
            g[es[i].a].pub(es[i].b);
            g[es[i].b].pub(es[i].a);
        }
    }
    dsu.init(n);
    rep(i,1,n)vis[i]=false;
    vis[rt]=true;
    for(auto son:g[rt]){
        dfs(son,son);
    }
    rep(i,1,m){
        if(use[i])continue;
        if(dsu.same(es[i].a,es[i].b)||es[i].a==rt||es[i].b==rt)continue;
        dg[es[i].a]++;dg[es[i].b]++;
        int fa = dsu.find(es[i].a), fb = dsu.find(es[i].b);
        if(dg[fa] > dg[fb]) swap(fa, fb);
        dg[rt]--,dg[fb]--;
        if(dg[es[i].a]>n/2||dg[es[i].b]>n/2){
            dg[es[i].a]--;dg[es[i].b]--;
            dg[rt]++;dg[fb]++;
            continue;
        }
        assert(dg[es[i].a]<=n/2&&dg[es[i].b]<=n/2&&dg[fb]<=n/2);
        use[i]=true;
        use[dte[fb]]=false;
        dsu.merge(fb,fa);
        if(dg[rt]<=n/2)break;
    }
    if(dg[rt]<=n/2)outans();
    else cout<<"No\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve();
    return 0;
}