题目描述

小明画了一棵树，有 $n$ 个点，$n-1$ 条边。红红画了另一棵树，也有 $n$ 个点，$n-1$ 条边。节点编号都是 $1\sim n$。

小明希望进行尽可能少的修改，把他的树变成红红的树。具体来说，每次修改他都可以添加一条边，然后删除一条边。

请你在保证修改次数最少的前提下，输出一种修改方案。

如果你不知道什么是树：

• 你可以把“边”当做是无所谓顺序的两个不相等的正整数，$(1,3)$ 是边，$(5,3)$ 也是边，$(3,5)$ 与 $(5,3)$ 是相同的边。
• 你可以把 $n$ 个点的“树”当做是无所谓顺序的 $n-1$ 条边。$(1,2),(3,2)$ 这两条边构成了一棵 $3$ 个点的树，这棵树与 $(3,2),(1,2)$ 以及 $(2,1),(3,2)$ 相同。但与 $(1,3),(3,2)$ 不相同。

输入格式

第一行一个数 $n$。

接下来 $n-1$ 行，每行两个数，为小明的树的 $n-1$ 条边，第 $i$ 行是第 $i$ 条边的两个端点。

再接下来 $n-1$ 行，每行两个数，为红红的树的 $n-1$ 条边，第 $i$ 行是第 $i$ 条边的两个端点。

输出格式

第一行一个数 $x$，为最少的修改次数。

接下来 $x$ 行，每行四个数 $a,b,x,y$，表示添加一条两个端点分别是 $a,b$ 的边，然后删除一条两个端点分别是 $x,y$ 的边（此时必须当前存在一条边，两个端点分别为 $x,y$）。

如果最少的修改次数正确，并且在你的修改操作后，“小明的树”与“红红的树”边的构成相同，那么则认为方案正确（即如果有多种修改次数最少的方案，输出任意一种都行）。

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

2
1 4 1 5
5 3 4 5

样例解释 1

• 初始小明的树四条边为：$(2,3)$、$(3,1)$、$(5,1)$、$(5,4)$
• 添加 $(1,4)$，删除 $(1,5)$ 后，会变成 $(2,3)$、$(3,1)$、$(5,4)$、$(1,4)$
  • $(1,5)$ 与 $(5,1)$ 是同一条边，原本第三条边 $(5,1)$ 被删除了
• 添加 $(5,3)$，删除 $(4,5)$ 后，最终会变成 $(2,3)$、$(3,1)$、$(1,4)$、$(5,3)$

这与红红的四条边 $(1,4)$、$(2,3)$、$(3,1)$、$(5,3)$ 构成相同。

显然如果输出下面的答案也是正确的

2
5 3 1 5
4 1 4 5

数据规模与约定

对于 $100\%$ 的数据，$3 \le n \le 10^5$，两个人的边都能构成合法的树，且至少要修改一次。

• 子任务 1（30 分）：$1\le n\le 1000$。
• 子任务 2（30 分）：保证一开始小明与红红只有一条边不同，剩下的 $n-2$ 条边都相同。
• 子任务 3（40 分）：没有特殊限制。