CF1284F.New Year and Social Network

Donghyun's new social network service (SNS) contains $n$ users numbered $1, 2, \ldots, n$. Internally, their network is a tree graph, so there are $n-1$ direct connections between each user. Each user can reach every other users by using some sequence of direct connections. From now on, we will denote this primary network as $T_1$.

To prevent a possible server breakdown, Donghyun created a backup network $T_2$, which also connects the same $n$ users via a tree graph. If a system breaks down, exactly one edge $e \in T_1$ becomes unusable. In this case, Donghyun will protect the edge $e$ by picking another edge $f \in T_2$, and add it to the existing network. This new edge should make the network be connected again.

Donghyun wants to assign a replacement edge $f \in T_2$ for as many edges $e \in T_1$ as possible. However, since the backup network $T_2$ is fragile, $f \in T_2$ can be assigned as the replacement edge for at most one edge in $T_1$. With this restriction, Donghyun wants to protect as many edges in $T_1$ as possible.

Formally, let $E(T)$ be an edge set of the tree $T$. We consider a bipartite graph with two parts $E(T_1)$ and $E(T_2)$. For $e \in E(T_1), f \in E(T_2)$, there is an edge connecting ${e, f}$ if and only if graph $T_1 - {e} + {f}$ is a tree. You should find a maximum matching in this bipartite graph.

东贤新开发的社交网络服务（SNS）包含 $n$ 个用户，编号为 $1, 2, \ldots, n$。其内部网络结构是一棵树图，因此用户之间共有 $n-1$ 条直接连接。任意两个用户均可通过若干条直接连接相互到达。此后，我们将该主网络记为 $T_1$。

为防止可能出现的服务器宕机，东贤构建了一个备份网络 $T_2$，它同样以一棵树图的形式连接相同的 $n$ 个用户。当系统发生故障时，$T_1$ 中恰好一条边 $e \in T_1$ 将变得不可用。此时，东贤将通过从备份网络 $T_2$ 中选取另一条边 $f \in T_2$ 并将其加入当前网络，来“保护”边 $e$。新增的这条边 $f$ 应能使整个网络重新恢复连通性。

东贤希望为尽可能多的边 $e \in T_1$ 分配一条替换边 $f \in T_2$。然而，由于备份网络 $T_2$ 较为脆弱，每条边 $f \in T_2$ 最多只能被指定为 $T_1$ 中至多一条边的替换边。在此约束下，东贤希望最大化被保护的 $T_1$ 中的边数。

形式化地，设 $E(T)$ 表示树 $T$ 的边集。我们构造一个二分图，其两部分顶点集分别为 $E(T_1)$ 和 $E(T_2)$。对任意 $e \in E(T_1)$ 和 $f \in E(T_2)$，当且仅当图 $T_1 - \{e\} + \{f\}$ 仍是一棵树时，$e$ 与 $f$ 之间存在一条边。你需要求出该二分图的一个最大匹配。

The first line contains an integer $n$ ($2 \le n \le 250\,000$), the number of users.

In the next $n-1$ lines, two integers $a_i$, $b_i$ ($1 \le a_i, b_i \le n$) are given. Those two numbers denote the indices of the vertices connected by the corresponding edge in $T_1$.

In the next $n-1$ lines, two integers $c_i$, $d_i$ ($1 \le c_i, d_i \le n$) are given. Those two numbers denote the indices of the vertices connected by the corresponding edge in $T_2$.

It is guaranteed that both edge sets form a tree of size $n$.

第一行包含一个整数 $n$（$2 \le n \le 250\,000$），表示用户数量。

接下来的 $n-1$ 行中，每行给出两个整数 $a_i$、$b_i$（$1 \le a_i, b_i \le n$），表示树 $T_1$ 中某条边所连接的两个顶点的编号。

再接下来的 $n-1$ 行中，每行给出两个整数 $c_i$、$d_i$（$1 \le c_i, d_i \le n$），表示树 $T_2$ 中某条边所连接的两个顶点的编号。

保证这两组边均构成大小为 $n$ 的树。

In the first line, print the number $m$ ($0 \leq m \lt n$), the maximum number of edges that can be protected.

In the next $m$ lines, print four integers $a_i, b_i, c_i, d_i$. Those four numbers denote that the edge $(a_i, b_i)$ in $T_1$ is will be replaced with an edge $(c_i, d_i)$ in $T_2$.

All printed edges should belong to their respective network, and they should link to distinct edges in their respective network. If one removes an edge $(a_i, b_i)$ from $T_1$ and adds edge $(c_i, d_i)$ from $T_2$, the network should remain connected. The order of printing the edges or the order of vertices in each edge does not matter.

If there are several solutions, you can print any.

第一行输出整数 $m$（$0 \leq m \lt n$），表示最多可保护的边数。

接下来 $m$ 行，每行输出四个整数 $a_i, b_i, c_i, d_i$。这四个数表示：将 $T_1$ 中的边 $(a_i, b_i)$ 替换为 $T_2$ 中的边 $(c_i, d_i)$。

所有输出的边必须分别属于其对应的网络，且在各自网络中对应互不相同的边。若从 $T_1$ 中删除边 $(a_i, b_i)$ 并添加 $T_2$ 中的边 $(c_i, d_i)$，则该网络仍需保持连通。边的输出顺序以及每条边中两个顶点的顺序均无关紧要。

若存在多种解法，输出任意一种即可。