#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
struct node{
    int u,v;
}e[maxn];
vector<pair<int,int> > G[maxn];
bool vis[maxn];
int n,m,f[maxn],times[maxn],fa[maxn],dep[maxn];
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])
	{
        if(to.first==pre) continue;
        dfs(to.first,u,t);
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while (T--){
        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] = {u,v};
   		 	int x = findx(u),y = findx(v);
    		if(x==y) continue;
			G[u].push_back({v,i});
   			G[v].push_back({u,i});
   			f[x]=y;
			vis[i]=1;
			times[u]++;
			times[v]++;
        }
        int rt = 0;
        for(int i=1;i<=n;++i) if(times[i]>n/2) rt=i;
        if(n==3)
		{
            printf("No\n");
            continue;
        }
        f[rt]=rt;
		dep[rt]=0;
        for(auto to:G[rt])
		{
            fa[to.first]=to.second;	
            dfs(to.first,rt,to.first);
        }
        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(times[x]>times[y]) 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;
}