#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 300100
vector<int> ed[N];
bool v[N];
bool banv[N];
int cnt=0;
vector<int> ans;
void dfs(int x)
{
	++cnt;
	v[x]=1;
	int len=ed[x].size();
	for(int i=0;i<len;++i)
	{
		int tar=ed[x][i];
		if(!v[tar])
		{
			dfs(tar);
		}
	}
}
void work(int x,bool ch)
{
	v[x]=0;
	int len=ed[x].size();
	if(ch)
	{
		ans.push_back(x);
		for(int i=0;i<len;++i)
		{
			int tar=ed[x][i];
			banv[tar]=1;
		}
		for(int i=0;i<len;++i)
		{
			int tar=ed[x][i];
			if(v[tar])
			{
				work(tar,!ch);
			}
		}
	}
	else
	{
		for(int i=0;i<len;++i)
		{
			int tar=ed[x][i];
			if(v[tar]&&banv[tar]==0)
			{
				work(tar,!ch);
			}
		}
	}
}
int main()
{	
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	int T;
	cin>>T;
//	freopen("1.out","w",stdout);
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		cnt=0;
		for(int i=1;i<=n;++i)
		{
			ed[i].clear();
			v[i]=0;
			banv[i]=0; 
		}
		for(int i=1;i<=m;++i)
		{
			int u,v;
			cin>>u>>v;
			ed[u].push_back(v);
			ed[v].push_back(u);
		}
		dfs(1);
		if(cnt==n)cout<<"YES\n";
		else
		{
			cout<<"NO\n";
			continue;
		}
		ans.clear();
		work(1,1);
		int len=ans.size();
		cout<<len<<endl;
		for(auto &i:ans)cout<<i<<" ";
		cout<<endl;
	}
}