水影若深蓝：挺好的一道并查集构造题。

观察

不难发现“距离为 \(2\)”这个条件我们可以通过黑白染色实现，我们把他们的中转点染成与他们相反的颜色，把这两个距离为 \(2\) 的点染成相同颜色。

这个染色问题就很并查集。

于是我们用并查集维护相同的种类。

显然，当图上只有一个连通块的时候，无解；否则我们一定可以找到一组解，因为一棵树一定可以进行黑白染色。

另一种理解就是距离为 \(2\) 是有传递性的。我们可以构造一个菊花，先钦定一个颜色不同的点（不在同一个连通块内），然后把某连通块所有的点与它连边，就可以让他们之间的距离全部为 \(2\)。

感觉和 Parity Game 里维护奇偶性的两个连通块思路差不多，但是这题更难描述出来一些。

构造

我们选择两个处于不同连通块的祖先 \(p_1,p_2\)，然后对于祖先非 \(p_1\) 的点，我们连一条向 \(p_1\) 的边；否则连 \(p_2\)。

最后注意 \(p_1\) 不能连任何边即可。

代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define lc (p<<1)
#define rc ((p<<1)|1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int f[300005],n,m,a[300005],b[300005];
void init()
{
	for(int i=1;i<=n;i++)f[i]=i;
}
int findf(int x)
{
	if(f[x]!=x)f[x]=findf(f[x]);
	return f[x];
}
void combine(int x,int y)
{
	int fx=findf(x),fy=findf(y);
	f[fx]=fy;
}
void solve()
{
	cin>>n>>m;
	init();
	for(int i=1;i<=m;i++)
	{
		cin>>a[i]>>b[i];
		combine(a[i],b[i]);
	}
	bool ilg=1;
	for(int i=1;i<=n;i++)
	{
		if(i>1)ilg=(ilg&(findf(i)==findf(i-1)));
	}
	if(ilg==1)
	{
		cout<<"No"<<endl;
		return;
	}
	cout<<"Yes"<<endl;
	int p1=-1,p2=-1;
	for(int i=1;i<=n;i++)
	{
		int fa=findf(i);
		if(p1==-1)p1=fa;
		else if(p2==-1&&fa!=p1)p2=fa;
	}
	for(int i=1;i<=n;i++)
	{
		int fa=findf(i);
		if(i==p1)continue;
		if(fa==p1)cout<<i<<" "<<p2<<endl;
		else cout<<i<<" "<<p1<<endl;
	}
	cout<<endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}