/*
	Luogu name: Symbolize
	Luogu uid: 672793
*/
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define rep1(i,l,r) for(register int i=l;i<=r;++i)
#define rep2(i,l,r) for(register int i=l;i>=r;--i)
#define rep3(i,x,y,z) for(register int i=x[y];~i;i=z[i])
#define rep4(i,x) for(auto i:x)
#define debug() puts("----------")
const int N=5e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
using namespace std;
int t,n,m,fa[N],times[N],f[N],dep[N];
bool vis[N];
vector<pii> G[N];
struct Graph{int u,v;}e[N];
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
int find(int x)
{
	if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void dfs(int x,int Fa,int top)
{
	dep[x]=dep[Fa]+1;
    fa[x]=top;
    rep4(to,G[x])
	{
        if(to.x==Fa) continue;
        dfs(to.x,x,top);
    }
    return;
}
void getans()
{
	n=read();
	m=read();
    rep1(i,1,n)
	{
		G[i].clear();
		fa[i]=i;
		times[i]=0;
	}
    rep1(i,1,m) vis[i]=0;
    rep1(i,1,m)
	{
        e[i].u=read();
        e[i].v=read();
	 	int x=find(e[i].u),y=find(e[i].v);
		if(x==y) continue;
		G[u].push_back(make_pair(v,i));
		G[v].push_back(make_pair(u,i));
		fa[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");
        return;;
    }
    fa[rt]=rt;
	dep[rt]=0;
    rep4(to,G[rt])
	{
        f[to.x]=to.y;	
        dfs(to.x,rt,to.x);
    }
    for(int i=1;i<=m;i++)
	{
        if(times[rt]<=n/2) break;
        int u=e[i].u,v=e[i].v;
        int x=find(u),y=find(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[f[y]]=0;
        fa[y]=x;
    }
    if(times[rt]>n/2) printf("No\n");
    else
    {
	    printf("Yes\n");
	    rep1(i,1,m) if(vis[i]) printf("%d %d\n",e[i].u,e[i].v);
	}
	return;
}
signed main()
{
	t=read();
    while(t--) getans();
    return 0;
}

answer.code: In function ‘void getans()’:
answer.code:58:10: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   58 |     rep1(i,1,n)
      |          ^
answer.code:10:38: note: in definition of macro ‘rep1’
   10 | #define rep1(i,l,r) for(register int i=l;i<=r;++i)
      |                                      ^
answer.code:64:10: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   64 |     rep1(i,1,m) vis[i]=0;
      |          ^
answer.code:10:38: note: in definition of macro ‘rep1’
   10 | #define rep1(i,l,r) for(register int i=l;i<=r;++i)
      |                                      ^
answer.code:65:10: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   65 |     rep1(i,1,m)
      |          ^
answer.code:10:38: note: in definition of macro ‘rep1’
   10 | #define rep1(i,l,r) for(register int i=l;i<=r;++i)
      |                                      ^
answer.code:71:19: error: ‘u’ was not declared in this scope
   71 |                 G[u].push_back(make_pair(v,i));
      |                   ^
answer.code:71:42: error: ‘v’ was not declared in this scope
   71 |                 G[u].push_back(make_pair(v,i));
      |                                          ^
answer.code:111:18: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  111 |             rep1(i,1,m) if(vis[i]) printf("%d %d\n",e[i].u,e[i].v);
      |                  ^
answer.code:10:38: note: in definition of macro ‘rep1’
   10 | #define rep1(i,l,r) for(register int i=l;i<=r;++i)
      |                                      ^
answer.code:111:45: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
  111 |             rep1(i,1,m) if(vis[i]) printf("%d %d\n",e[i].u,e[i].v);
      |                                            ~^       ~~~~~~
      |                                             |            |
      |                                             int          long long int
      |                                            %lld
answer.code:111:48: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘long long int’ [-Wformat=]
  111 |             rep1(i,1,m) if(vis[i]) printf("%d %d\n",e[i].u,e[i].v);
      |                                               ~^           ~~~~~~
      |                                                |                |
      |                                                int              long long int
      |                                               %lld