P11479 [NordicOI 2017] Subway

译自 Nordic Olympiad in Informatics 2017 [Subway](https://noi17.kattis.com/contests/vfoqp8/problems/subway4)。 本题 SPJ 是搬题人自己写的，在 。如果发现有误请联系搬题人。

斯德哥尔摩的地铁系统非常低效。由于城市的布局已经发生了变化，某些部分使用过度，而某些线路几乎无人使用。 因此，市议会决定重建地铁系统。目前，系统由 $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$ 的轨道。

你的解法将在一组子任务上进行评分。每个子任务包含多个测试用例。要获得子任务的分数，你的解法必须通过子任务中的所有测试用例。 | 子任务 | 分数 | 限制条件 | | ------ | ---- | ------------ | | $1$ | $33$ | $N\leq 10$ | | $2$ | $33$ | $N\leq 1000$ | | $3$ | $34$ | $N\leq 10^5$ |