40pts，后面的 subtask 很多mle，但是感觉没有开很多啊/yun 求救

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5+5;

int n,_d;

struct tree {
	int deg,rt;
	vector<int> g[N];
	void init(){
		for (int i=1; i<n; i++){
			int u,v;
			cin>>u>>v;
			g[u].push_back(v);
			g[v].push_back(u);
		} 
	}
	void fd_deg(){
		deg=0;
		for (int i=1; i<=n; i++){
			deg=max(deg,(int)g[i].size());
		}
	}
} t1,t2; 

vector<int> lf;
vector<int> G[N];

void dfs(int u,int fa){
	for (auto v : t2.g[u]){
		if (v^fa){
			dfs(v,u);
		}
	}
	if (fa && t2.g[u].size()==1){
		lf.push_back(u);
		return;
	}
	for (auto v : t2.g[u]){
		if (v^fa){
			int dg=t2.g[v].size();
			if (dg!=t2.deg){
				G[u].push_back(v);
				G[v].push_back(u);
			}
			else{
				int w=lf.back();
				G[u].push_back(w);
				G[w].push_back(u);
				lf.pop_back();
			}
		}
	}
}

int fz[N],idx;
vector<int> ans[N];

void dfs1(int u,int fa){
	fz[u]=fa;
	for (auto v : G[u]){
		if (v^fa){
			dfs1(v,u);
		}
	}
}

void mod(){
	for (int i=1; i<=n; i++) G[i].clear();
	int rt=1;
	for (int i=1; i<=n; i++){
		if (t2.g[i].size()==1) rt=i;
	}
	int pre=t2.deg;
	lf.clear();
	dfs(rt,0);
	dfs1(rt,0);
	vector<int> ad;
	for (int i=1; i<=n; i++) ad.push_back(fz[i]);
	ans[++idx]=ad;
	for (int i=1; i<=n; i++){
		swap(t2.g[i],G[i]);
	}
	t2.fd_deg();
	t2.rt=rt;
	if (t2.deg>=pre) assert(0);
}

int p[N],tot,rk[N];

void dfsp(int u,int fa){
	p[++tot]=u;
	rk[u]=tot;
	for (auto v : t2.g[u]){
		if (v^fa){
			dfsp(v,u);
		}
	}
}

int f[N];

int ff(int x){
	return x==f[x]?x:f[x]=ff(f[x]); 
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>_d;
	if (n==2){
		cout<<"1\n0 1\n";
		return 0;
	}
	t1.init();
	t2.init();
	t2.fd_deg();
	t1.rt=1;
	for (int i=1; i<=n; i++){
		if (t2.g[i].size()==1) t2.rt=i;
	}
	for (int i=1; i<=n; i++) G[i]=t2.g[i];
	dfs1(t2.rt,0);
	vector<int> ad;
	for (int i=1; i<=n; i++) ad.push_back(fz[i]);
	ans[++idx]=ad;
	while (t2.deg!=2){
		mod();
	}
	assert(t2.g[t2.rt].size()==1);
	dfsp(t2.rt,0);
	for (int i=1; i<=n; i++){
		f[i]=i;
		G[i].clear();
		fz[i]=0;
	}
	for (int i=1; i<=n; i++){
		// 按照 p_i 的顺序
		for (auto j : t1.g[p[i]]){
			int k=ff(j);
			if (rk[k]<i){
				f[k]=p[i];
				G[p[i]].push_back(k);
				G[k].push_back(p[i]);
			}
		}
	} 
	dfs1(p[n],0);
	ad.clear();
	for (int i=1; i<=n; i++) ad.push_back(fz[i]);
	ans[++idx]=ad;
	reverse(ans+1,ans+1+idx);
	cout<<idx<<"\n";
	for (int i=1; i<=idx; i++){
		auto u=ans[i];
		for (auto v : u) cout<<v<<" ";
		cout<<"\n";
	} 
	return 0;
}