思路先把其分成两个块使得两个块没有边相连 再在其中选两个点使这两个点相连 然后将一个点与和它不在同一个连通块的点相连

#include<bits/stdc++.h>
using namespace std;
int t,n,m,vis[300010],l,cnt;
vector<int> v[300010];
struct node
{
	int u,v;
};
node g[300010];
void dfs(int x)
{
	if(vis[x]) return;
	vis[x]=1;
	for(int i:v[x]) dfs(i);
}
signed main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		if(m==0)
		{
			cout<<"Yes\n";
			continue;
		}
		cnt=0;l=0;
		memset(vis,0,sizeof vis);
		memset(g,0,sizeof g);
		for(int i=1;i<=m;i++)
		{
			int x,y;
			cin>>x>>y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		dfs(1);
		for(int i=1;i<=n;i++)
		{
			if(vis[i]==0)
			{
				l=i;
				break;
			}
		}
		if(l==0){
			cout<<"No\n";
			continue;
		}
		cout<<"Yes\n";
		for(int i=1;i<=n;i++)
		{
			if(vis[i]==1&&i!=1)
			{
				g[++cnt]={l,i};
			}
			if(vis[i]==0&&i!=l)
			{
				g[++cnt]={1,i};
			}
		}
		g[++cnt]={1,l};
		for(int i=1;i<=cnt;i++)
		{
			cout<<g[i].u<<' '<<g[i].v<<endl;
		}
	}
	return 0;
}

WA on Subtask #1 #2 #3 #7