题目背景

译自 Nordic Olympiad in Informatics 2017 Subway。

本题 SPJ 是搬题人自己写的，在 https://www.luogu.com/paste/7l4p6s3h。如果发现有误请联系搬题人。

题目描述

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

因此，市议会决定重建地铁系统。目前，系统由 $N$ 个车站组成，这些车站通过 $N−1$ 对轨道连接，保证任意两个车站之间都可以通过地铁到达。议会制定了一个新的计划，仍然包含相同的 $N$ 个车站，但轨道将更换为另一组 $N−1$ 条轨道（同样保证所有车站之间连通）。

为了尽量减少繁忙地铁的中断，重建必须一次进行一条轨道的更换。每个周末，将关闭一条轨道并修建一条新的轨道。这意味着系统始终保留 $N−1$ 条轨道。此外，在每个周末施工后，任意两个车站之间仍需保持连通。

你的任务是设计一个施工方案，使得以上条件成立，并且所需的周末数量最少。

输入格式

第一行包含一个整数 $1\leq N$。接下来的 $N−1$ 行描述当前地铁系统的轨道。每条轨道由两个以空格分隔的整数 $a$ 和 $b$ 表示，分别是轨道连接的车站编号（$0$ 到 $N−1$ 的编号，基于 $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

提示

你的解法将在一组子任务上进行评分。每个子任务包含多个测试用例。要获得子任务的分数，你的解法必须通过子任务中的所有测试用例。