我的名字是詹姆斯·迪格里兹,我是整个银河系最聪明的强盗和寻宝者。有一些关于我的冒险经历的书和关于我的手术的歌曲,尽管你能够在一个相当尴尬的时刻抓住我。
我躲过了摄像头,智胜了所有守卫,并通过了无数陷阱,但当我最终到达宝箱并打开它时,我不小心启动了发条炸弹!幸运的是,我以前遇到过这种炸弹,我知道可以通过以某种方式连接炸弹控制面板上的电线触点来停止发条机构。
我看到 n 个触点由 n - 1 根电线连接。联系人用 1 到 n 之间的整数进行编号。 Bomb具有确保以下条件的安全机制:如果存在k≥2个触点c1,c2,...,ck形成电路,i。 e.触点c1和c2、c2和c3、...、ck和c1之间存在k条不同的电线,然后炸弹立即爆炸,我的故事到此结束。特别是,如果两个触点通过多于一根导线连接,它们会形成长度为 2 的电路。也禁止触点与其自身连接。
另一方面,如果我断开多于一根电线(即在某个时刻,方案中不会有超过 n - 2 根电线),则其他安全检查失败,炸弹也会爆炸。所以,我唯一能做的就是拔掉一些电线并将其插入新的地方,确保没有电路出现。
我知道应该如何放置电线才能停止发条。但我的时间已经不多了!帮助我活着离开这里:找到操作顺序,每个操作都包括拔掉一些电线并将其放在另一个地方,以便拆除炸弹。
输入
输入的第一行包含触点数量 n (2 ≤ n ≤ 500 000)。
以下 n - 1 行中的每一行都包含两个整数 xi 和 yi (1 ≤ xi, yi ≤ n, xi ≠ yi),表示当前由第 i 根电线连接的触点。
剩余的 n - 1 行包含相同格式的所寻求方案的描述。
保证开始和结束方案是正确的(即不包含与其自身连接的电路或电线)。
输出
第一行应包含 k (k ≥ 0) — 拆除炸弹所需的拔出和插回一些电线的最少移动次数。
在接下来的 k 行中,每行输出四个整数 ai、bi、ci、di,这意味着在第 i 步中,需要拔下连接触点 ai 和 bi 的电线,然后将其插入触点 ci 和 di。当然,线路连接触点ai和bi应该出现在该方案中。
如果没有正确的序列将现有方案转换为所寻求的方案,则输出-1。
示例
输入 #1
3 1 2 2 3 1 3 3 2
输出 #1
1 1 2 1 3
输入 #2
4 1 2 2 3 3 4 2 4 4 1 1 3
输出 #2
3 1 2 1 3 4 3 4 1 2 3 2 4
注意
示例测试说明图片: