题目描述

题目译自 NordicOI 2017 T1 「Subway」

斯德哥尔摩的地铁系统非常低效。由于城市布局已经发生了变化，某些地铁线路过度使用，而另一些线路几乎无人问津。

因此，市议会决定重建地铁系统。目前，地铁系统由 $N$ 个车站组成，$N - 1$ 对车站通过轨道连接，使得可以在任意两个车站之间乘坐地铁。市议会制定了一个新计划，仍然包含相同的 $N$ 个车站，但使用另一组 $N - 1$ 条轨道（仍然保证所有车站都连接）。

为了尽量减少对繁忙地铁的干扰，重建必须一次只进行一条轨道的更换。每个周末，关闭一条旧轨道并建造一条新轨道。这意味着始终会有 $N - 1$ 条轨道。此外，在每个周末的施工期间，必须始终能够在任意两个车站之间旅行。

你的任务是找到一种重建新地铁网络的方法，确保这些条件得到满足。你的计划必须使用尽可能少的周末。

输入格式

第一行包含一个整数 $N$。接下来的 $N - 1$ 行描述当前地铁系统中的轨道。每条轨道由两个用空格分隔的整数 $a$ 和 $b$ 组成，表示连接的车站的编号（编号从 $0$ 开始）。可以通过这些轨道在任意两个车站之间旅行。

接下来的 $N - 1$ 行描述新地铁系统中的轨道，格式相同。

输出格式

首先输出你的施工计划需要的周末数 $K$。然后输出 $K$ 行，每行包含四个整数 $a_1, b_1, a_2, b_2$，表示关闭连接 $a_1$ 和 $b_1$ 的轨道，并建造连接 $a_2$ 和 $b_2$ 的轨道。

3
0 1
1 2
0 1
0 2

1
2 1 2 0

4
0 1
0 2
0 3
0 1
1 2
2 3

2
3 0 3 2
0 2 1 2

数据范围与提示

详细子任务附加限制及分值如下表所示。