看到比赛的时候zzq大聚聚用了LCT做的，在线%%%
首先，我们可以发现，两棵大小相同、构造形状不同的树，一定是可以用另一棵树的边来维持这棵树上的每一个点的相互连通性的。我的做法，就是基于这样展开的，
我们有T1、T2两棵树，现在我们要去用T2树上的边，来代替T1树上的边，使得代替的边能保持原树的连通性。
看到如图的树左边的T1和右边的T2，两边的颜色相互对应原边与代替边。
这里用贪心的策略来解决这个问题。
我们看到如图的T2，对于T2 的叶子结点，它和它的父亲结点，只能用来维护一次联通，那么这个联通应该用在哪里？用在叶子结点往父亲结点最近的点，这是最贪心的策略，譬如说T2图中的2号点和9号点，我们的2号点只能用一次来维护联通了，而剩余的点都是还可以用来维护的，所以，转换到图一中去，我们应该最贪心的将2号点和4号点（图T1）所链接的边用2-9（T2）边代替，尽管它是可以代替（2-4）、（4-7）、（7-9）这条链上的所有的边，但是这样的贪心策略却是最优的。
我们现在就是想办法去维护这个，那么不妨就是从那些只有一个可以链接的点x开始出发，它在T2中所唯一链接的且没有被使用过的点y，那么，基于贪心的策略，我们将它在T1中的对应x的所在位置，向它的y在T1中所在位置的这一条链找出来，我们要用xy这条边来替换这条链上距离x最近的未被替换的边。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 250005;
int N;
struct Graph
{
int head[maxN], cnt, du[maxN], root[maxN], fa[maxN][20], deep[maxN];
inline int _LCA(int u, int v)
{
if(deep[u] < deep[v]) swap(u, v);
int det = deep[u] - deep[v];
for(int i=log2(det); i>=0; i--)
{
if((det >> i) & 1) u = fa[u][i];
}
if(u == v) return u;
for(int i=log2(N); i>=0; i--)
{
if(fa[u][i] ^ fa[v][i])
{
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
inline int fid(int x) { return x == root[x] ? x : root[x] = fid(root[x]); }
void init()
{
for(int i=1; i<=N; i++)
{
head[i] = -1;
du[i] = 0;
root[i] = i;
}
cnt = 0;
}
struct Eddge
{
int nex, to;
Eddge(int a=-1, int b=0):nex(a), to(b) {}
}edge[maxN << 1];
inline void addEddge(int u, int v)
{
edge[cnt] = Eddge(head[u], v);
head[u] = cnt++;
}
inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); }
void dfs(int u, int father)
{
fa[u][0] = father; deep[u] = deep[father] + 1;
for(int i=0; (1 << (i + 1)) < N; i++) fa[u][i + 1] = fa[fa[u][i]][i];
for(int i=head[u], v; ~i; i=edge[i].nex)
{
v = edge[i].to;
if(v == father) continue;
dfs(v, u);
}
}
}T1, T2;
bool vis[maxN] = {false};
queue<int> Q;
void tp_sort()
{
for(int i=1; i<=N; i++) if(T2.du[i] == 1) Q.push(i);
while (Q.size() > 1) //保证至少有两个端点，保证可以构成边
{
int u = Q.front(), x = 0, y = 0; Q.pop();
vis[u] = true;
x = u;
for(int i=T2.head[u], v; ~i; i=T2.edge[i].nex)
{
v = T2.edge[i].to;
if(!vis[v])
{
y = v;
T2.du[v]--;
if(T2.du[v] == 1) Q.push(v);
}
}
int p = T1._LCA(x, y);
int fix = T1.fid(x), fiy;
if(T1.deep[fix] > T1.deep[p]) //如果深度更深，先要保证x与自己的临近父亲的在树上的链接性
{
printf("%d %d %d %d\n", T1.fa[fix][0], fix, x, y);
T1.root[fix] = T1.fid(T1.fa[fix][0]);
}
else //如果深度更浅的话，先要保证上面结点的连通性
{
fiy = y;
for(int i=log2(N); i>=0; i--)
{
if(T1.deep[T1.fa[fiy][i]] > T1.deep[p] && (T1.fid(T1.fa[fiy][i]) ^ fix)) fiy = T1.fa[fiy][i];
}
printf("%d %d %d %d\n", fiy, T1.fa[fiy][0], x, y);
T1.root[fiy] = fix;
}
}
}
int main()
{
scanf("%d", &N);
T1.init(); T2.init();
for(int i=1, u, v; i<N; i++)
{
scanf("%d%d", &u, &v);
T1._add(u, v); T1.du[u]++; T1.du[v]++;
}
for(int i=1, u, v; i<N; i++)
{
scanf("%d%d", &u, &v);
T2._add(u, v); T2.du[u]++; T2.du[v]++; //保证贪心策略先从度为1的点开始选取
}
T1.deep[0] = 0;
T1.dfs(1, 0);
printf("%d\n", N - 1);
tp_sort();
return 0;
}