说明

给定你大小为 $n$，两棵树 $S,T$，定义对 $S$ 的一次操作为：

• 选择 $S$ 的任意一条直径 $(p,q)$。
• 选择任意一个这条直径上的点 $u$，再选择与 $u$ 相邻的一个不在这条直径上的点 $v$，再选择这条直径上的另一个点 $w$，执行操作：
• 断开 $(u,v)$ 的连边，连接 $(v,w)$。

你需要判断，是否可以让 $S$ 通过任意次操作得到 $S'$，使得 $S'$ 与 $T$ 同构。如果可以，你需要在 $4n$ 次数内输出一种方案。

输入格式

第一行输入一个正整数 $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$，代表你构造方案的操作次数。

你需要保证你的操作次数小于等于 $4n$ 次，如果你的操作次数超过了 $4n$，将会被判定为 Wrong Answer。

接下来 $k$ 行每行你需要输出五个整数 $(p_i,q_i,u_i,v_i,w_i)$，代表你的一次操作。

接下来你需要输出一行 $p_i$，代表操作后的 $S$ 树中 $x$ 对应 $T$ 树的 $p_x$。

本题开启 Special Judge，如果你正确输出了 $\texttt{Yes}$ 或者 $\texttt{No}$，你会得到该子任务 $20\%$ 的分数。注意：如果你输出了 $\texttt{Yes}$，请一定在后面输出一个方案（尽管可能是不合法的，你可以直接输出 $n+1$ 个 $0$ 来达到这一点）。

7
1 2
2 3
3 7
3 4
4 5
5 6
7 6
6 5
5 4
4 3
3 2
3 1

Yes
1
1 6 3 7 5
7 6 5 4 3 2 1

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

No

提示

本题采用捆绑测试。

• Subtask 1（5 pts）：$n \le 10$。
• Subtask 2（5 pts）：保证 $S$ 为一条链。
• Subtask 3（5 pts）：保证 $T$ 为一条链。
• Subtask 4（5 pts）：保证 $S$ 为菊花。
• Subtask 5（10 pts）：保证 $S,T$ 仅有一条直径，且所有度数 $> 2$ 的点只存在于直径上。
• Subtask 6（10 pts）：保证 $S,T$ 初始直径长度相同。
• Subtask 7（25 pts）：$n \le 500$。
• Subtask 8（35 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le a_i,b_i,c_i,d_i \le n \le 2 \times 10^3$。

在结束所有旅程，陷入沉眠时。

我一定会回到这个夏天的吧。