#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
const int M = 2e5+10;
int n,m;
int ans = 0 ;
int cnt = 0;
int cnt_tree ;
int inde[M] ;
int flag ;
struct edge{
	int x,y;
//	int w;
}a[M];
struct edge_tree{
	int x,y;
//	int w;
}e[M];

bool cmp(edge_tree a,edge_tree b)		//排序 
{
	if(a.x>b.x) return a.x<b.x;
	if(a.x == b.x) return a.y < b.y ;
}

int f[M];
int find(int x)		//并查集 
{
	if(f[x]==x) return x;
	return f[x] = find(f[x]);
}
void kru()
{
	for(int i = 1 ; i <= n ; i++ )		//并查集初始化 
	{
		f[i] = i ;   
		inde[i] = 0;
	}
//	sort(a+1,a+m+1,cmp);
	cnt_tree = 0 ;
//	inde[M] = {0};
	flag = 0;
	for(int i = 1; i <= m ; i++)
	{
		int eu = find(a[i].x);
		int ev = find(a[i].y);
		if(eu == ev) continue;
		e[++cnt_tree].x = min(a[i].x,a[i].y);
		e[cnt_tree].y = max(a[i].x,a[i].y);
		f[ev] = eu;
		if(cnt_tree==n-1)
		{
			break;
		}
	}
}
void slove()
{
	cin>>n>>m;
	for(int i = 1 ; i <= m ; i++ )
	{
		int x,y;//,z;
		cin>>x>>y;//>>z;
		a[i].x=x;
		a[i].y=y;   
	//	a[i].w=z;      
	}
/*	for(int i = 1 ; i <= n ; i++ )		//并查集初始化 
	{
		f[i] = i ;   
	}*/
	kru();
	sort(e+1,e+cnt_tree+1,cmp);
	for(int i = 1 ; i <= cnt_tree ; i++ )
	{
		inde[e[i].x]++;
		inde[e[i].y]++;
//		cout<<e[i].x<<" "<<e[i].y<<endl;
	}
	for(int i = 1 ; i <= cnt_tree ; i++ )
	{
		if( inde[i] > n/2 )
		{
			flag = 1 ;
			break;
		}
	}
/*	for(int i = 1 ; i <= cnt_tree ; i++ )
	{
		cout<<inde[i]<<" ";
		
	}*/
	if(flag == 0 )
	{
		cout<<"Yes"<<endl;
		for(int i = 1 ; i <= cnt_tree ; i++ )
			cout<<e[i].x<<" "<<e[i].y<<endl;
		return ;
	}
	cout<<"No"<<endl;
}
int main()
{

	int tcase;
	cin>>tcase;
	while(tcase--)
	{
		slove();
	}
	return 0;
	
}