P15416 「yrOI R1」夏日已逝


给定你大小为 $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$ 来达到这一点）。

**本题采用捆绑测试**。 + 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$。 ----------------- 在结束所有旅程，陷入沉眠时。 我一定会回到这个夏天的吧。