斯德哥尔摩的地铁系统效率非常低下。现在的城市面貌与地铁线路修建时已大不相同，这意味着某些路段过度拥挤，而另一些线路几乎无人问津。

因此，市议会决定重建地铁系统。目前，该系统由 $N$ 个车站组成，共有 $N-1$ 条轨道连接这些车站，使得任意两个车站之间都可以通过地铁到达。议会制定了一项新计划，该计划同样包含这 $N$ 个车站，但采用了另一组 $N-1$ 条轨道（同样保证所有车站连通）。

为了尽量减少对繁忙地铁系统的干扰，重建工作必须一次只处理一条轨道。每个周末，必须关闭一条旧轨道并修建一条新轨道。这意味着系统中始终保持有 $N-1$ 条轨道。此外，在每个周末的施工之后，必须始终保证任意两个车站之间都是连通的。

你的任务是找到一种构建新地铁网络的方法，使得上述条件成立。你的计划必须使用尽可能少的周末。

输入格式

第一行包含整数 $1 \le N$。接下来的 $N-1$ 行描述了当前地铁系统中的轨道。每条轨道由两个 $0$ 到 $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$ 的轨道。

子任务

你的解决方案将在多组子任务上进行评测。一个子任务包含多个测试用例。为了获得子任务的分数，你的解决方案必须通过该子任务中的所有测试用例。

样例

样例输入 1

3
0 1
1 2
0 1
0 2

样例输出 1

1
2 1 2 0

样例输入 2

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

样例输出 2

2
3 0 3 2
0 2 1 2