题目背景

君が見たい世界を見られるように 希望能够看到你想见到的世界

僕は今日も手を引くよ 今天我也会拉住你的手

どこまでも沈んだって 无论下沉到哪里

底を走る僕を見て 即使看见我在海底奔跑

嘲笑う人がいたって 有人发出不屑嘲笑

君と行きたいんだ 我也想和你一同前行

——海底列車 - PIKASONIC / なこたんまる

题目描述

我们对一棵树定义一次操作为，选择两个距离为偶数的节点 $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}$，请一定在后面输出一个方案（尽管可能是不合法的）。

10
1 2
1 8
1 4
1 7
2 9
3 5
3 8
5 10
6 8
1 9
1 2
1 5
1 6
9 8
8 3
5 10
6 4
6 7

Yes
2
9 3
5 7
1 9 8 2 5 4 3 6 7 10

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

No

提示

本题采用捆绑测试。

• 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$。

---

初音一度闭上眼睛，然后睁开。宠物靠近吸血姬。

狂妄地用手指示吸血姬蹲下。吸血姬念着「哎呀哎呀」，照她说的弯下了腰。初音嫌弃地在吸血姬鼻尖上吻了一下。

幼小的吸血姬挂着温柔的表情要对初音讲话，就像小孩子让爱猫爬到自己腿上一样。

鼻子和鼻子碰在一起，就像要讲悄悄话，

就像要讲一个永恒不变的，重要的事实。

「最喜欢你了」