#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],times[maxn],fa[maxn],dep[maxn];
void add(int u,int v,int id)
{
    
}
int findx(int x)
{
    return f[x]==x?x:f[x]=findx(f[x]);
}
void dfs(int u,int pre,int t)
{
	dep[u]=dep[pre]+1;
    f[u]=t;
    for(auto to:G[u])
	{
        int v=to.v;
        if(v==pre) continue;
        dfs(v,u,t);
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while (T--){
        int n,m,rt = 0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) 
		{
			G[i].clear();
			f[i]=i;
			times[i]=0;
		}
        for(int i=1;i<=m;i++) vis[i]=0;
        for(int i=1;i<=m;i++) 
		{
            int u,v;
            scanf("%d%d",&u,&v);
            e[i] = node(u,v,i);
   		 	int x = findx(u),y = findx(v);
    		if(x==y) continue;
			G[u].push_back(node(u,v,i));
   			G[v].push_back(node(v,u,i));
   			f[x]=y;
			vis[i]=1;
			times[u]++;
			times[v]++;
        }
        for(int i=1;i<=n;++i) if(times[i]>n/2) rt=i;
        if(n==3)
		{
            printf("No\n");
            continue;
        }
        dep[rt] = 0,f[rt] = rt;
        for(auto to:G[rt])
		{
            fa[to.v]=to.id;	
            dfs(to.v,rt,to.v);
        }
        for(int i=1;i<=m;i++){
            if(times[rt]<=n/2) break;
            int u=e[i].u,v=e[i].v;
            int x=findx(u),y=findx(v);
            if(x==y||u==rt||v==rt) continue;
            if(dep[u]<dep[v]) swap(u,v),swap(x,y);
            if(dep[v]==1&&times[u]>times[v]) swap(u,v),swap(x,y);
            ++times[u];
			++times[v];
			--times[rt];
			--times[y];
            vis[i]=1;
			vis[fa[y]]=0;
            f[y]=x;
        }
        if(times[rt]>n/2) printf("No\n");
        else
        {
		    printf("Yes\n");
		    for(int i=1;i<=m;i++){
		        if(vis[i]) printf("%d %d\n",e[i].u,e[i].v);
		    }
		}
    }
    return 0;
}