CF650E.Clockwork Bomb

My name is James diGriz, I'm the most clever robber and treasure hunter in the whole galaxy. There are books written about my adventures and songs about my operations, though you were able to catch me up in a pretty awkward moment.

I was able to hide from cameras, outsmart all the guards and pass numerous traps, but when I finally reached the treasure box and opened it, I have accidentally started the clockwork bomb! Luckily, I have met such kind of bombs before and I know that the clockwork mechanism can be stopped by connecting contacts with wires on the control panel of the bomb in a certain manner.

I see n contacts connected by n - 1 wires. Contacts are numbered with integers from 1 to n. Bomb has a security mechanism that ensures the following condition: if there exist k ≥ 2 contacts _c_1, _c_2, ..., c__k forming a circuit, i. e. there exist k distinct wires between contacts _c_1 and _c_2, _c_2 and _c_3, ..., c__k and _c_1, then the bomb immediately explodes and my story ends here. In particular, if two contacts are connected by more than one wire they form a circuit of length 2. It is also prohibited to connect a contact with itself.

On the other hand, if I disconnect more than one wire (i. e. at some moment there will be no more than n - 2 wires in the scheme) then the other security check fails and the bomb also explodes. So, the only thing I can do is to unplug some wire and plug it into a new place ensuring the fact that no circuits appear.

I know how I should put the wires in order to stop the clockwork. But my time is running out! Help me get out of this alive: find the sequence of operations each of which consists of unplugging some wire and putting it into another place so that the bomb is defused.

我的名字是詹姆斯·迪格里兹，我是整个银河系最聪明的劫匪和寻宝者。关于我的冒险故事被写成了书，关于我的行动也被谱成了歌，不过你恰好在我一个相当尴尬的时刻抓住了我。

我成功躲过了所有摄像头，智胜了全部守卫，并通过了无数陷阱；但当我终于抵达宝箱并将其打开时，却不慎启动了发条炸弹！幸运的是，我之前曾遇到过这种炸弹，我知道：只要以特定方式用导线连接炸弹控制面板上的触点，就能停止发条机构。

我看到有 $ n $ 个触点，由 $ n-1 $ 根导线相互连接。触点编号为 $ 1 $ 到 $ n $ 的整数。炸弹配备了一种安全机制，确保如下条件成立：若存在 $ k \geq 2 $ 个触点 $ c_1, c_2, \dots, c_k $ 构成一个回路（即存在 $ k $ 条互不相同的导线，分别连接触点对 $ c_1 $ 与 $ c_2 $、$ c_2 $ 与 $ c_3 $、……、$ c_k $ 与 $ c_1 $），则炸弹会立即爆炸，我的故事也就此终结。特别地，若两个触点之间存在多于一根导线，则它们构成一个长度为 $ 2 $ 的回路。此外，也不允许将某个触点与其自身相连。

另一方面，若我断开超过一根导线（即在某一时刻，整个电路中剩余导线数量不超过 $ n-2 $ 根），则另一项安全检测将失败，炸弹同样会爆炸。因此，我唯一能做的操作是：拔下某一根导线，并将其重新插入另一个位置，同时确保不产生任何回路。

我知道该如何布置这些导线才能停住发条机构。但我的时间所剩无几！请帮我活下来：找出一系列操作，每次操作均包含拔下某一根导线并将其插到新位置，最终使炸弹成功拆解。

The first line of the input contains n (2 ≤ n ≤ 500 000), the number of contacts.

Each of the following n - 1 lines contains two of integers x__i and y__i (1 ≤ x__i, y__i ≤ n, x__i ≠ y__i) denoting the contacts currently connected by the i-th wire.

The remaining n - 1 lines contain the description of the sought scheme in the same format.

It is guaranteed that the starting and the ending schemes are correct (i. e. do not contain cicuits nor wires connecting contact with itself).

输入的第一行包含一个整数 $n$（$2 \leq n \leq 500\,000$），表示接触点的数量。

接下来的 $n-1$ 行中，每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq n$，且 $x_i \neq y_i$），表示第 $i$ 根导线当前连接的两个接触点。

随后的 $n-1$ 行以相同格式描述目标连接方案。

保证初始方案和目标方案均合法（即均不包含环路，且不存在连接同一接触点的导线）。

The first line should contain k (k ≥ 0) — the minimum number of moves of unplugging and plugging back some wire required to defuse the bomb.

In each of the following k lines output four integers a__i, b__i, c__i, d__i meaning that on the i-th step it is neccesary to unplug the wire connecting the contacts a__i and b__i and plug it to the contacts c__i and d__i. Of course the wire connecting contacts a__i and b__i should be present in the scheme.

If there is no correct sequence transforming the existing scheme into the sought one, output -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$。

Picture with the clarification for the sample tests:

用于说明样例测试的图示：