#5433. 「OOI 2016 Day 1」时钟装置

题目描述

题目译自 Open Olympiad in Informatics 2016 Day1 T3 「Часовой механизм / Clockwork Bomb」。

我叫吉姆·迪·格里兹，是整个银河系中最狡猾的骗子和冒险家。关于我的冒险经历，人们写下了无数书籍，我的抢劫事迹更是数不胜数。然而，此刻你却发现我陷入了一个非常棘手的处境。

我成功躲过了摄像头，智胜了数十名守卫，绕过了无数陷阱，终于到达了梦寐以求的宝箱。然而，当我打开箱盖时，却触发了一枚带有时钟装置的炸弹，秒针已经开始倒计时，爆炸迫在眉睫！幸运的是，我之前曾遇到过类似型号的炸弹，知道可以通过正确连接控制面板上的接触点与导线来停止时钟装置。

面前有 $n$ 个接触点，通过 $n - 1$ 条导线连接。接触点编号从 $1$ 到 $n$。炸弹的设计是这样的：如果某组 $k \geq 2$ 个接触点 $c_1, c_2, \ldots, c_k$ 形成一个循环，即接触点对 $c_1$ 和 $c_2$、$c_2$ 和 $c_3$、$\ldots$、$c_k$ 和 $c_1$ 之间存在 $k$ 条不同的导线，那么安全检查会立即触发，炸弹瞬间爆炸，留下不走运的拆弹者无迹可寻。特别地，如果两个接触点之间连接了多条导线，则会形成长度为 $2$ 的循环，炸弹同样会爆炸。禁止将接触点与自身连接。

另一方面，如果我同时拔下超过一条导线（换句话说，某一时刻连接的导线少于 $n - 2$ 条），则会触发另一项安全检查，结果同样是灾难性的。因此，我唯一能做的就是依次拔下一条导线并将其插入新的位置，确保在此过程中不形成连接接触点的循环。

我知道如何排列导线才能停止时钟装置。但我的时间越来越少！请帮助我摆脱困境：找到最短的安全操作序列，每一步操作包括拔下一条特定导线并将其连接到新位置，同时最终排列导线以达到目标状态。

输入格式

第一行包含一个整数 $n$ $(2 \leq n \leq 500000)$，表示接触点的数量。

接下来的 $n - 1$ 行，每行包含两个整数 $x_i$ 和 $y_i$ $(1 \leq x_i, y_i \leq n, x_i \neq y_i)$，表示当前连接的导线两端的接触点编号。

再接下来的 $n - 1$ 行以相同格式描述停止时钟装置所需的导线连接方案。

输出格式

第一行输出一个整数 $k$ $(k \geq 0)$，表示需要重新连接的最小导线数量。

接下来的 $k$ 行，每行输出四个整数 $a_i, b_i, c_i, d_i$，表示在第 $i$ 步操作中，应拔下连接接触点 $a_i$ 和 $b_i$ 的导线，并用它连接接触点 $c_i$ 和 $d_i$。当然，此时连接 $a_i$ 和 $b_i$ 的导线必须存在于当前方案中。

如果存在多个最优序列，可以输出其中任意一个。

如果无法找到所需的操作序列，则输出一个数字 $-1$。

样例 1

输入

3
1 2
2 3
1 3
3 2

输出

1
1 2 1 3

样例相关的解释图片如下：

样例 2

输入

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

输出

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

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	测试点编号	分值	附加限制	备注
1	$3 \sim 18$	$20$	$n \leq 50$	保证答案存在且所需操作不超过 $1$ 次
2	$19 \sim 37$
3	$38 \sim 53$		$n \leq 5000$
4	$54 \sim 69$		$n \leq 100000$
5	--		无特殊限制