题目描述

给定两棵均包含 $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$ 的合法方案。

Sol

本题解约定，记 $(a,b),(c,d)\longrightarrow(e,f),(g,h)$ 表示删除 $(a,b),(c,d)$，加入 $(e,f),(g,h)$。

---

先说说原题构造的无解情况。

无解的情况其实是很好理解的，只要 $T_1$ 在变换为 $T_2$ 前无法操作了即无解。无法操作的情况，就是任选两条不同的边都会有一个公共点的情况，这种情况下显然会存在一个节点的度数是 $n-1$，即 $T_1$ 是菊花。

如果 $T_1$ 一开始就是菊花，那么仅当 $T_2$ 和 $T_1$ 在边集上完全相同，才能说构造次数 $=0$；否则，$T_1$ 根本动不了，自然就是无解。

下面就是要证明，除了上面所述的这种情况外，其他的 $T_1$ 都能用 $<n$ 次变换出来 $T_2$。

---

特殊性质 $A$ 其实也真的挺特殊的，况且这是一个非常非常好做的性质，所以证明的开始就拿这种情况来说吧。

特殊性质 $A$ 其实就是只需不断把尚未与中心 $P$ 相连的点改挂到 $P$ 上（开始就没有和中心尚未相连的点，那么就意味着原图是菊花，这种就被特判掉了），每次让 $\deg(P)$ 增加 $1$，这样的话至多操作 $n-2$ 次。

---

接下来就是最难的部分了。

考虑选一个 $T_1$ 中当前度数至少是 $2$ 的点（由于当前树不是菊花，这个点一定有），定为最后结果的根（分析用的根，题目中树本身没根）。对两个树进行考虑的时候都以这个根考虑，暂且称这个根是 $R$。

接下来按照 $T_2$ 中从根到叶子的顺序处理，使得已经构造好的目标边不会再被真正破坏。

考虑我们要构造出 $T_2$ 中有而当前没有的一个边 $(u,v)$，这里只考虑 $u$ 的父亲 $f$ 已经构造好并且 $u$ 和 $f$ 已经连上了的情况（无父亲时特殊考虑但同理）。

先消一些可能会对之后的操作产生阻碍的情况。

第一种就是，如果 $v$ 当前是叶子，而 $v$ 构造后应该有儿子 $w$，但是当前有边 $(u,w)$，那么如果直接接 $(u,v)$ 就会出现 $v-u-w$ 的造型，这样有共点的话就很难处理了。这时候，我们设 $v$ 到 $u$ 路径上，从 $v$ 遇到的第一个非端点点是 $a$，那么就有 $(a,v)$ 和 $(u,w)$ 了，此时可以 $(a,v),(u,w)\longrightarrow(u,v),(v,w)$。特别地，如果 $a=w$，那么造型就是 $v-w-u$ 了，但是我们想让造型变成 $w-v-u$，这时候我们可以找一个避开 $w$ 的边 $(x,y)$（选择时要避免共点产生），然后先把 $v$ 摘下来（也就是 $(v,w),(x,y)\longrightarrow(v,x),(x,y)$），然后再 $(v,x),(u,w)\longrightarrow(v,w),(u,v)$，就可以了（注意，此处删 $(a,v)$ 时需要核验其是否会进入下面第二种情况）。

第二种情况，就是如果删了 $(a,v)$，导致 $a$ 变成叶子了，而 $a$ 现在唯一的邻点（这里称为 $b$）上连着 $a$ 在目标中的儿子 $c$，那么就会有 $a-b-c$ 这种结构了，导致 $c$ 难以变化到 $a$ 上。这种时候，显然不能直接删除 $(a,v)$，而是 $(a,v),(b,c)\longrightarrow(a,v),(a,c)$（特别地，如果 $u=b$ 应该 $(a,v),(b,c)\longrightarrow(b,v),(a,c)$，如果 $u=c$ 应该 $(a,v),(b,c)\longrightarrow(a,c),(c,v)$），先做一步变换再搞原先的 $(a,v)$。注意这种情况中不特殊的操作后要重新考虑下两点之间路径。

第三种是防止构造卡死的，就是如果 $u$ 度数是 $n-2$，那么再把 $v$ 接到 $u$ 就会菊花，导致操作卡死。此时我们可以造一个不经过 $u$ 的目标边，这样就能防止操作卡死了。具体的变换方法，需要在 $T_2$ 中有形如 $u-x-y$ 这样的链（当前的 $v$ 要放到 $u$，此时如果没有避开当前 $u-a-v$ 的类似链就会导致目标图是菊花，但是目标图不是菊花，所以这个链必然有）（显然这里 $y$ 还没放上去），这里设 $a$ 是 $v$ 唯一的邻点，那么如果 $x=a$ 则 $(v,a),(u,y)\longrightarrow(u,v),(a,y)$，如果 $x\ne a$ 则 $(v,a),(u,x)\longrightarrow(v,x),(u,x),\quad(v,x),(u,y)\longrightarrow(x,y),(u,v)$（注意这个 $x$ 不能乱选，要考虑到有无前面的情况）。

处理好这三种情况之后就可以开始构造了。如果处理完上面情况没顺带建立目标边，那么就分类讨论：如果 $u$ 到 $v$ 路径长度 $>2$ 可以一步构造；如果 $u-a-v$ 但是 $u$ 除 $a$ 外还有相邻的点那么也可以一步成立；如果 $u-a-v$ 且 $u$ 已经是叶子了那么可以利用当前图非菊花的性质找边转移（$(u,a),(x,y)\longrightarrow(u,x),(x,y)$ 然后 $(u,x),(a,v)\longrightarrow(u,v),(u,a)$）。

为什么只需要处理这三种情况呢？其实这三种情况有迹可循，且三种情况综合在一起已经处理了所有可能出问题的点。具体地，第一种情况负责了新连上的 $v$ 的问题（防止了 $v$ 的儿子挂不上），第二种情况负责了操作时被删边 $(a,v)$ 的问题（比较像第一种，是为了防止 $a$ 的儿子挂不上），第三种情况负责了全图继续操作（不卡死）的可能性。

---

构造部分的最后一个关键就是操作次数的证明了。

正常情况下，每个非根节点需要一次操作接到目标父亲，因此先按 $n-1$ 次计算。

如果某条目标父边本来就存在，或者一次操作同时接好了两个点，就会省下一次操作。把每次省下的操作记下来，留给其中唯一可能在以后需要两步转移的点。

而需要两步转移的点，每次只会额外多花一步。前面对于费劲情况的预处理保证没有省过操作的点不会突然进入这种情况；并且一个点完成两步转移后，就不会再次触发（就是说，一个点需要两次构造，都是因为这个点是叶子，且这个点目标中要构造的儿子挂在这个点目前的唯一一个邻点上（这导致需要依赖外部合适的边去辅助作这个转移）。这种两次构造情况，要不然是在刚接上时出现的（情况一），要不然是在删其邻边时出现的（情况二），也就是能够进入这种状态的节点，之前一定因为“目标父边原本存在 / 被其他操作顺带连上”而省下过一次操作，一个节点完成两步构造后目标父边和一条目标子边都已经接好，也就不会再触发两步构造，同时省下的操作次数为其多出来的操作次数找补出来了（情况三不会增加两步构造的次数，这里不考虑），那么构造次数就是正确的了）。

一共省下 $S$ 次，有 $H$ 次两步构造出来的，则 $H\le S$。所以总操作次数为 $m=(n-1)-S+H\le n-1<n$。

构造部分的题解就到此结束了。

---

对 LCT 等实现进行的描述，对正确的实现没有特别大的辅助作用，所以直接讲 std 最后的实现思路。

最终实现中，将当前树固定个根（前面讲了），维护每个点的父亲、父边编号和邻接表（链表实现）。这样可以在常数时间内判断一条边是否存在，并完成删边、加边，还可以局部修改父子关系。

构造中需要反复查询某个目标的儿子是否通过一条非目标边挂在指定节点上，而由于构造的过程不会永久加入新的非目标边（可能因为构造需要而临时建立），所以这类边只可能来自初始的树，因此可以预先对相关信息排序，查询时二分找到候选的边（跳过已经失效的边）。

构造顺序同前文即可。

于是最后的时间复杂度就是 $O(n\log n)$，空间复杂度 $O(n)$。