这是一个老坑了，今天终于填上了，先放一个题目链接：https://codeforces.com/problemset/problem/1559/D2。

题目大意如下。初始给你两个森林，为了方便我们将其简称为f1和f2，|f1|,|f2|分别代表f1,f2的树的数量，然后现在让你去决定两个点u,v，分别将f1和f2的u，v相连，并且要保证两张图上不能出环。最后输出最多能连出几条边，并且输出每次的u，v。

先来说思路，首先有个显而易见的特点，如果暴力去枚举u，v在两边的并查集都没有重合的情况下，这样能枚举出最大的连接方式。最多能连出min(|f1|,|f2|)-1条边，具体参照本题easy版。这里主要探讨更快的做法，n方毕竟会超时。

题解那个方法真给我看蒙了，submission里面有一巨佬的写法简单易懂，我直呼牛逼，下面来介绍一下。

先考虑一下最终都被合并完的状态，设|f1|<=|f2|，最终肯定是f1被连接的只剩一个树了。那我们不妨先去找一棵树作为一个中心点，例如1号节点所在的树。然后枚举2~n如果点i在f1，f2当中都和1不在同一集合中那就让两个森林的1和i连接。然后，接下来是重点，再次枚举2~n，如果其中一个森林里i和1在同一集合中另一个不在。开两个栈，把这种情况下的i点存入不在同一集合的那个栈里。最后两个栈没有交集，在两个栈里取出两个栈顶数字连接，这样便可得到最终代码。在下面贴一张代码方便理解

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int fa1[N],fa2[N];
vector<pair<int,int> >ans;
int find(int* fa,int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa,fa[x]);
}
int main(){
	int n,m1,m2;
	cin>>n>>m1>>m2;
	for(int i=1;i<=n;i++) fa1[i]=i,fa2[i]=i;
	for(int i=1;i<=m1;i++){
		int u,v;
		cin>>u>>v;
		fa1[find(fa1,u)]=find(fa1,v);
	}
	for(int i=1;i<=m2;i++){
		int u,v;
		cin>>u>>v;
		fa2[find(fa2,u)]=find(fa2,v);
	}
	int rt=1;
	//cout<<find(fa2,rt)<<" "<<find(fa2,5);
	for(int i=1;i<=n;i++){
		if(find(fa1,i)!=find(fa1,rt)&&find(fa2,i)!=find(fa2,rt)){
			ans.push_back({rt,i});
			fa1[find(fa1,i)]=find(fa1,rt);
			fa2[find(fa2,i)]=find(fa2,rt);
		}
	}
	stack<int>s1;
	stack<int>s2;
	for(int i=1;i<=n;i++){
		if(find(fa1,i)!=find(fa1,rt)&&find(fa2,i)==find(fa2,rt)) s1.push(i);
		if(find(fa1,i)==find(fa1,rt)&&find(fa2,i)!=find(fa2,rt)) s2.push(i);
	}
	while(s1.size()&&s2.size()){
		int u=s1.top(),v=s2.top();
		ans.push_back({u,v});
		fa1[find(fa1,u)]=find(fa1,rt);
		fa2[find(fa2,v)]=find(fa2,rt);
		while(s1.size()&&find(fa1,s1.top())==find(fa1,rt)) s1.pop();
		while(s2.size()&&find(fa2,s2.top())==find(fa2,rt)) s2.pop();
	}
	cout<<ans.size()<<endl;
	for(int i=0;i<ans.size();i++)
		cout<<ans[i].first<<" "<<ans[i].second<<endl;
	return 0;
}