WA42pts求调

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
struct union_find {
	int fa[100000];
	void make_set (int n) {
		for (int i=0;i<n;i++) this->fa[i]=i;
	}
	int find_root (int x) {
		if(x==-1) return x;
		if (x!=this->fa[x]) this->fa[x]=find_root(this->fa[x]);
		return this->fa[x];
	}
	void union_set (int x,int y) {
		if (x==y) return ;
		if(x>y) swap(x,y);
		if(x==-1) return ;
		x=find_root(x);
		y=find_root(y);
		if(x>y) swap(x,y);
		this->fa[x]=y;
	}
};
vector<int> G[2000],G2[2000],l[2000],set[2000];
		int fa[2000],fa2[2000],d[2000],fd[2000][2000];
int dfs1(int u,int dep) {
	for (int i=0;i<G[u].size();i++) dfs1(G[u][i],dep+1);
	d[u]=dep;
	l[dep].push_back(u);
}
int dfs2(int u,int dep) {
	if (d[u]==dep) return fd[u][dep]=u;
	for (int i=0;i<G2[u].size();i++) fd[u][dep]=max(fd[u][dep],dfs2(G2[u][i],dep));
	return fd[u][dep];
}
int main() {
	int t;
	cin>>t;
	while (t--) {
		int n,m;
		cin>>n;
		for (int i=0;i<1500;i++) {
			G[i].clear();
			G2[i].clear();
			l[i].clear();
			set[i].clear();
			memset(fd[i],-1,sizeof(fd[i]));
		}
		memset(d,0,sizeof(d));
		memset(fa,-1,sizeof(fa));
		memset(fa2,-1,sizeof(fa2));
		for (int i=1;i<n;i++) {
			int f,t;
			cin>>t>>f;
			f--,t--;
			G[f].push_back(t);
			fa[t]=f;
		}
		cin>>m;
		for (int i=1;i<m;i++) {
			int f,t;
			cin>>t>>f;
			f--,t--;
			G2[f].push_back(t);
			fa2[t]=f;
		}
		//cout<<endl;
		int dep=0;
		for (int i=0;i<n;i++) if(fa[i]==-1) {
			dfs1(i,0);
			//cout<<i<<endl;
		}
		//cout<<endl; 
		for (int i=0;i<n;i++) dep=max(dep,d[i]);
		dep++;
		for (int i=0;i<n;i++) if(fa[i]==-1) {
			for (int j=0;j<dep;j++) dfs2(i,j);
			//cout<<i<<endl;
		}
		union_find un;
		un.make_set(n);
		for (int i=0;i<n;i++) {sort(G[i].begin(),G[i].end());sort(G2[i].begin(),G2[i].end());}
		for (int i=0;i<dep;i++) sort(l[i].begin(),l[i].end());
		////<<endl;
		for (int i=0;i<n;i++) {
			un.union_set(fa[i],fa2[i]);
			int u=fa[i],v=fa2[i];
			////<<i<<' '<<u<<' '<<v<<endl;
			while((u!=-1)&&(v!=-1)&&(un.find_root(fa[u])!=un.find_root(fa[v]))) {
				un.union_set(fa[u],fa[v]);
				u=fa[u],v=fa[v];
				////<<u<<' '<<v<<endl;
			}
		}
		//cout<<endl;
		////<<endl;
		for (int i=0;i<n;i++) {
			if(G2[i].size()==0) continue;
			for (int j=0;j<(G2[i].size()-1);j++) {
				int u=G2[i][j],v=G2[i][j+1];
				u=fa[u],v=fa[v];
				un.union_set(u,v);
				//<<i<<' '<<u<<' '<<v<<endl;
				while((u!=-1)&&(v!=-1)&&(un.find_root(fa[u])!=un.find_root(fa[v]))) {
					un.union_set(fa[u],fa[v]);
					u=fa[u],v=fa[v];
				////<<u<<' '<<v<<endl;
				}
			}
		}
		//cout<<endl;
		for (int i=0;i<n;i++) un.find_root(i);
		for (int i=0;i<n;i++) {
			if(fa2[i]+1||G2[i].size()) {
				//set[un.fa[i]].push_back(i);
				//<<i<<endl;
			}
			else {
				if (un.find_root(i)!=i) {
					//set[un.find_root(i)].push_back(i);
					continue;
				}
				int u=un.find_root(fa[i]);
				while (!(fa2[u]+1||G2[u].size()||un.find_root(i)-i)) u=un.find_root(fa[u]);
				u=un.find_root(u);
				u=fd[u][d[i]];
				un.union_set(u,i);
			}
		}
		//for (int i=0;i<n;i++) cout<<fd[i][2]<<endl;
		//cout<<endl;
		for(int i=0;i<n;i++) set[un.find_root(i)].push_back(i);
		cout<<(n-m)<<endl;
		for (int i=0;i<dep;i++) {
			for (int j=0;j<l[i].size();j++) {
				int u=l[i][j];
				for (int k=0;k<set[u].size();k++) if(set[u][k]!=u) cout<<(set[u][k]+1)<<' '<<(u+1)<<endl;
			}
		}
		//for (int i=0;i<n;i++) //<<d[i]<<' '; 
	}
	return 0;
}