#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
struct node{
    int u,v,id;
    node(int u=0,int v=0,int id=0):u(u),v(v),id(id){}
}e[maxn];
vector<node>G[maxn];
bool vis[maxn];
int f[maxn],in[maxn],fa[maxn],dep[maxn];
void add(int u,int v,int id){
    G[u].push_back(node(u,v,id));
    G[v].push_back(node(v,u,id));
}
int findx(int x){
    return f[x]==x?x:f[x] = findx(f[x]);
}
void unite(int x,int y){
    x = findx(x),y = findx(y);
    if(x==y) return ;
    f[x] = y;
}
bool same(int x,int y){
    return findx(x)==findx(y);
}
void dfs(int u,int pre,int t){
    f[u] = t,dep[u] = dep[pre]+1;
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i].v;
        if(v==pre) continue;
        dfs(v,u,t);
    }
}
void print(int m){
    printf("Yes\n");
    for(int i=1;i<=m;i++){
        if(vis[i]) printf("%d %d\n",e[i].u,e[i].v);
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while (T--){
        int n,m,rt = 0;
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++) f[i] = i,G[i].clear(),in[i] = 0;
        for(int i=0;i<=m;i++) vis[i] = false;
        for(int i=1;i<=m;i++) {
            int u,v;
            scanf("%d%d",&u,&v);
            e[i] = node(u,v,i);
            if(!same(u,v)) unite(u,v),vis[i] = true,in[u]++,in[v]++,add(u,v,i);
            if(in[u]>in[rt]) rt = u;
            if(in[v]>in[rt]) rt = v;
        }
        if(n==3){
            printf("No\n");
            continue;
        }
        dep[rt] = 0,f[rt] = rt;
        for(int i=0;i<G[rt].size();i++){
            int v = G[rt][i].v;
            fa[v] = G[rt][i].id;
            dfs(v,rt,v);
        }
        for(int i=1;i<=m;i++){
            if(in[rt]<=n/2) break;
            int u = e[i].u,v = e[i].v;
            int fu = findx(u),fv = findx(v);
            if(fu==fv||u==rt||v==rt) continue;
            if(dep[u]<dep[v]) swap(u,v),swap(fu,fv);
            if(dep[v]==1&&in[u]>in[v]) swap(u,v),swap(fu,fv);
            ++in[u],++in[v],--in[rt],--in[fv];
            vis[e[i].id] = true,vis[fa[fv]] = false;
            f[fv] = fu;//!!!!
        }
        if(in[rt]>n/2) printf("No\n");
        else print(m);
    }
    return 0;
}