题目描述

给定两棵均包含 $n$ 个节点的无根树 $T_1, T_2$，节点编号均为 $1 \sim n$。

现在需要通过一系列“等价交换”操作将 $T_1$ 变成 $T_2$。

一次“等价交换”操作定义如下：

• 在当前的树中选择两条没有公共端点的边 $e_1 = (u, v)$ 和 $e_2 = (x, y)$。将这两条边删去。此时树会被断开成三个独立的连通块。你需要加入两条新的边，这两条新边的端点必须全部来自于集合 $\{u, v, x, y\}$。
  • 要求：加入新边后，整个图必须重新成为一棵连通的树。新边边集不得为 $\{e_1, e_2\}$。新边可以共端点。

现在需要构造一种操作方案，使树 $T_1$ 的边集完全变为 $T_2$ 的边集，或者告知不存在合法的操作方案。

注：本题中的树均为无向简单图。“等价交换”加入操作的两条边必须互不相同，且不得与“等价交换”删除操作后仍然存在的边重合。

输入格式

本题输入输出量较大，请使用较快的输入输出方式。

请注意常数因子对程序运行的影响。

第一行，一行两个整数 $c,n$，分别表示子任务编号与树的节点个数（样例中 $c=0$）。

接下来 $n-1$ 行，每行两个整数 $u, v$，表示树 $T_1$ 中存在一条连接 $u, v$ 的边。

再接下来 $n-1$ 行，每行两个整数 $u, v$，表示树 $T_2$ 中存在一条连接 $u, v$ 的边。

输出格式

如果不存在合法的操作方案，输出一行一个 $-1$。

否则，第一行输出一个非负整数 $m$，表示你的操作次数。

如存在合法操作方案且 $m>0$，则接下来 $m$ 行，每行描述一次操作，即每行输出八个整数 $u, v, x, y, u', v', x', y'$，表示你选择删去的两条边分别是 $(u, v)$ 和 $(x, y)$，加入的两条边分别是 $(u', v')$ 和 $(x',y')$（注：一定需要满足 $u, v, x, y$ 两两不同且 $u',v',x',y'\in\{u,v,x,y\}$。任何边的两个端点都不可相同）。

输入输出样例 #1

输入 #1

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

输出 #1

1
1 2 3 4 1 3 2 4

说明/提示

数据范围

对于 $100\%$ 的数据，保证 $4 \le n \le 10^6$，要求 $m<n$。

保证对本题的所有数据，若 $T_1$ 可以通过若干次交换转化为 $T_{2}$，则一定存在一个操作次数 $m<n$ 的合法方案。

---

先考虑无解情况，显然菊花图的任意两条边都是相邻的，所以无法操作，此时若 $T_1=T_2$，输出 $0$，否则输出 $-1$。接下来的构造将说明，只要 $T_1$ 不是菊花图，就可以在 $n-1$ 次操作内转为任意 $T_2$。

如果 $T_2$ 是菊花图，将所有点依次挂到中心即可，以下讨论 $T_2$ 不为菊花图的情况。

先选根 $r$，具体如何选会在后文讨论到，按照 $T_2$ 的 dfn 序遍历节点，先遍历 $T_2$ 的非叶儿子再遍历叶儿子。

对于节点 $v$，记 $x$ 为 $v$ 的当前父亲，$u$ 为 $v$ 的目标父亲，若 $x=u$，无需操作，否则，若能找到 $u$ 当前的一个邻居 $y\ne x$，就可以 $(v,x),(u,y)\longrightarrow(v,u),(u,y)$，相当于把 $v$ 的子树从 $x$ 接到 $u$ 上，显然能维持树的结构，称以上为“普通处理”。

但问题在于，如果 $u$ 只有一个邻居 $x$，找不到辅助边，就无法完成上述操作，为了解决这种情况，我们引入一类“特殊处理”。

如果节点 $v$ 是当前叶子，取 $v$ 的一个目标儿子 $w$，那么，希望在两步内接出 $u-v-w$（如果 $v$ 同时是目标叶子，普通处理即可），注意，这里可以保证 $u$ 有辅助边，原因将在后面提到。我们记 $y$ 为 $w$ 的当前父亲，接下来进行分讨。

若 $y\ne u$，先把 $v$ 接到 $u$，再 $(w,y),(v,u)\longrightarrow(w,v),(v,u)$ 把 $w$ 接到 $u$ 即可。

若 $y=u$，注意此时有一条 $(u,w)$ 的边，继续分讨。

若 $x\notin\{u,w\}$，直接 $(v,x),(w,u)\longrightarrow(v,u),(v,w)$，合法性比较显然。

若 $x\in\{u,w\}$，考虑取辅助边 $(p,q)$ 满足 $p\ne u,w$ 且 $q\ne a$，然后 $(v,a),(p,q)\longrightarrow(v,p),(p,q)$，再 $(v,p),(w,u)\longrightarrow(v,u),(v,w)$ 即可，简单解释一下：第一步是暂时把 $v$ 接到 $x$ 构造辅助边，第二步和上面那种情况基本相同。只要当前树不是菊花图，必然能找到这样的 $(p,q)$。

接下来分析为什么所有已经接好父亲的节点 $u$ 必然有辅助边：对于普通处理中接好的节点，会立马给其接上一个儿子（若为当前叶，则也为目标叶，跳过即可），而特殊处理中，$v$ 在处理后也接好了一个儿子，当然，$w$ 仍可能是当前叶子，但是，$v$ 此时唯二的邻居就是 $u$ 和 $w$，而之后接到 $v$ 的点显然是其目标儿子，故对于任意尚未接到其目标父亲的点，有其当前父亲不为 $v$，换句话说，在接 $w$ 的儿子时，$(v,w)$ 必然能作为辅助边。

综上，可以在均摊一步内将一个点接到其目标父亲上，接下来，我们要选一个合适的根，使得树不会突变为菊花图或增加操作次数。

我们发现，如果已经构造好一条长度至少为 $4$ 的链，那么树就不可能变成菊花图，记 $S=\{x\mid \deg_{T_1}(x)\ge2\}$，注意，这里使用的是初始 $T_1$ 的度数，由于 $T_1$ 不为菊花图，$|S|\ge 2$，进行分讨。

若 $\exist r\in S$ 且 $r$ 为目标叶子，以 $r$ 为根，$r$ 初始存在辅助边来接儿子，而且其只需要接一个儿子，不会造成阻碍，同时，其儿子必然存在一个目标非叶儿子，那么按照遍历顺序，开始就能接出长度为 $4$ 的链。

否则，若 $\exist u\in S$ 且其有目标叶儿子 $r$，仍以 $r$ 为根，由于第一类不存在，$r$ 在 $T_1$ 中也是叶子，若 $(r,u)$ 已经存在，跳过，否则，记 $r$ 的唯一邻居为 $x$，取 $u$ 的一个孩子 $v$，做 $(r,x),(u,v)\longrightarrow(r,u),(r,v)$ 就可以将 $u$ 接到 $r$，然后正常处理即可，证明同第一类。

若前两类都不存在，取 $T_2$ 中包含 $S$ 所有点的最小子树 $K$，取 $K$ 的一个叶子 $r$，显然 $r\in S$（不然 $r$ 就被去掉了），取 $r$ 的首个不属于 $K$ 的儿子 $x$，再取 $x$ 的首个儿子 $y$（必然存在，否则满足第一/二类），先遍历不属于 $S$ 的儿子，再遍历其他的，发现在处理前者时，$r$ 必然与 $S$ 中的一点连接，记为 $s$，而处理不会影响 $(r,s)$，故其可以作为辅助边，同时，开始便接好了 $s-r-x-y$ 的链，处理后者时，会直接将 $r$ 的一个属于 $S$ 的目标儿子 $z$ 接到 $r$，保持 $z-r-x-y$，且在之后都能保证 $r$ 有辅助边。

综上，我们讨论完了所有情况，构造部分到此结束。

发现这么做是有严格 $O(n)$ 的做法的，强于官解的 $O(nlogn)$，但码长有点非人，就不写了。