题目描述

斯德哥尔摩的地铁系统十分低效。

由于城市的发展已经和最初建设地铁线路时不同，有些线路负载很高，而有些线路几乎无人使用。因此，市议会决定重建地铁系统。

现在的地铁系统有 $N$ 个车站，由 $N-1$ 条轨道连接，并且任意两个车站之间都可以通过地铁互相到达。也就是说，现在的地铁系统是一棵树。

市议会已经制定了新的规划。新的地铁系统仍然包含相同的 $N$ 个车站，也包含 $N-1$ 条轨道，并且任意两个车站之间仍然可以互相到达。也就是说，新的地铁系统也是一棵树。

为了尽量减少对繁忙地铁系统的影响，重建工作必须一条轨道一条轨道地进行。

每个周末必须关闭一条已有轨道，并新建一条轨道。也就是说，任意时刻系统中都始终有 $N-1$ 条轨道。此外，在每个周末施工完成后，仍然必须保证任意两个车站之间可以互相到达。

请你构造一个重建方案，使得上述条件始终成立，并且使用的周末数尽可能少。

输入格式

第一行包含一个整数 $N$，表示车站数量。

接下来 $N-1$ 行，每行两个整数 $a,b$，表示当前地铁系统中有一条连接车站 $a$ 和 $b$ 的轨道。

接下来 $N-1$ 行，每行两个整数 $a,b$，表示新的地铁系统中需要有一条连接车站 $a$ 和 $b$ 的轨道。

车站编号为 $0$ 到 $N-1$。

保证当前地铁系统和目标地铁系统都是连通的树。

输出格式

第一行输出一个整数 $K$，表示你的施工方案需要的周末数。

接下来 $K$ 行，每行输出四个整数 $a_1,b_1,a_2,b_2$，表示这个周末关闭连接 $a_1,b_1$ 的轨道，并新建连接 $a_2,b_2$ 的轨道。

你的方案必须满足：

• 每一步关闭的轨道当前确实存在；
• 每一步新建的轨道当前不存在；
• 每一步施工后，整张图仍然是一棵连通图；
• 最后得到的地铁系统正好是目标地铁系统；
• $K$ 尽可能小。

样例输入

3
0 1
1 2
0 1
0 2

样例输出

1
2 1 2 0

数据范围与子任务

总限制：