P14464 海底列車（collapse）

>君が見たい世界を見られるように 希望能够看到你想见到的世界 > >僕は今日も手を引くよ 今天我也会拉住你的手 > >どこまでも沈んだって 无论下沉到哪里 > >底を走る僕を見て 即使看见我在海底奔跑 > >嘲笑う人がいたって 有人发出不屑嘲笑 > >君と行きたいんだ 我也想和你一同前行 > > _——[海底列車 - PIKASONIC / なこたんまる](https://music.163.com/#/song?id=1971812333)_

我们对一棵树定义一次操作为，选择两个距离为偶数的节点 $x,y(x \ne y)$，然后将整棵树的根变成 $(x,y)$ 路径上的一个点 $z$，记 $f_x,f_y$ 为 $x,y$ 此时的父亲。依次执行以下内容： + 断开边 $(x,f_x),(y,f_y)$。 + 连接边 $(x,f_y),(y,f_x)$。 你需要求出，两棵大小均为 $n$ 的树 $S$ 是否能够经过若干次操作变得与 $T$ 同构，如果可以，你还需要给出方案。

第一行输入一个正整数 $n$，代表树 $S$ 和树 $T$ 的大小。 接下来 $n-1$ 行，每行输入两个整数 $(a_i,b_i)$，代表树 $S$ 的一条边。 接下来 $n-1$ 行，每行输入两个整数 $(c_i,d_i)$，代表树 $T$ 的一条边。

第一行输出一个字符串 $\texttt{Yes}$ 或者 $\texttt{No}$，代表是否可以让 $S$ 通过操作与 $T$ 同构。 如果你输出了 $\texttt{Yes}$，接下来一行你需要输出一个数 $k$，代表你构造方案的操作次数。 你需要保证你的操作次数小于等于 $2n$ 次，如果你的操作次数超过了 $2n$，将会被判定为 Wrong Answer。 接下来 $k$ 行每行你需要输出两个整数 $(x_i,y_i)$，代表你的一次操作。 接下来你需要输出一行 $p_i$，代表操作后的 $S$ 树中 $x$ 对应 $T$ 树的 $p_x$。 本题开启 Special Judge，如果你正确输出了 $\texttt{Yes}$ 或者 $\texttt{No}$，你会得到该子任务 $20\%$ 的分数（每个子任务向下取整的加和）。注意：如果你输出了 $\texttt{Yes}$，请一定在后面输出一个方案（尽管可能是不合法的）。

**本题采用捆绑测试**。 + Subtask 1（1 pts）：$n \le 10$。 + Subtask 2（3 pts）：$n \le 20$。 + Subtask 3（1 pts）：保证 $S$ 为一条链。 + Subtask 4（11 pts）：保证 $S,T$ 均为毛毛虫。这里毛毛虫的定义是，存在一条链使得所有点到链的距离 $\le 1$。 + Subtask 5（11 pts）：如果可以从 $S$ 操作至 $T$，则保证存在一种操作方式，使得 $S$ 操作后和 $T$ 相同。 + Subtask 6（11 pts）：如果可以从 $S$ 操作至 $T$，则保证存在一种操作方式，使得 $S$ 操作不超过 $10$ 次和 $T$ 同构。 + Subtask 7（16 pts）：$n \le 800$。 + Subtask 8（46 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le a_i,b_i,c_i,d_i \le n \le 5 \times 10^3$。 ----------------- 初音一度闭上眼睛，然后睁开。宠物靠近吸血姬。 狂妄地用手指示吸血姬蹲下。吸血姬念着「哎呀哎呀」，照她说的弯下了腰。初音嫌弃地在吸血姬鼻尖上吻了一下。 幼小的吸血姬挂着温柔的表情要对初音讲话，就像小孩子让爱猫爬到自己腿上一样。 鼻子和鼻子碰在一起，就像要讲悄悄话， 就像要讲一个永恒不变的，重要的事实。 「最喜欢你了」