Background

Problem Description

You are given two trees $S, T$ of size $n$. Define one operation on $S$ as follows:

• Choose any diameter $(p, q)$ of $S$.
• Choose any node $u$ on this diameter, then choose a node $v$ adjacent to $u$ that is not on this diameter, then choose another node $w$ on this diameter, and perform:
• Delete the edge $(u, v)$, and add the edge $(v, w)$.

You need to determine whether it is possible to apply the operation any number of times to transform $S$ into some $S'$, such that $S'$ is isomorphic to $T$. If it is possible, you need to output one valid plan within $4n$ operations.

Input Format

The first line contains a positive integer $n$, which is the size of trees $S$ and $T$.

The next $n - 1$ lines each contain two integers $(a_i, b_i)$, representing an edge of tree $S$.

The next $n - 1$ lines each contain two integers $(c_i, d_i)$, representing an edge of tree $T$.

Output Format

Output a string $\texttt{Yes}$ or $\texttt{No}$ on the first line, indicating whether it is possible to make $S$ isomorphic to $T$ using the operations.

If you output $\texttt{Yes}$, then on the next line output an integer $k$, the number of operations in your constructed plan.

You must ensure that the number of operations is at most $4n$. If your number of operations exceeds $4n$, you will be judged as Wrong Answer.

In the next $k$ lines, output five integers $(p_i, q_i, u_i, v_i, w_i)$, describing one operation.

Then you need to output one line $p_i$, meaning that in the tree $S$ after all operations, node $x$ corresponds to node $p_x$ in tree $T$.

This problem uses a Special Judge. If you correctly output $\texttt{Yes}$ or $\texttt{No}$, you will get $20\%$ of the score for that subtask. Note: if you output $\texttt{Yes}$, you must output a plan afterwards (even if it may be invalid; you can directly output $n + 1$ zeros to do this).

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

Hint

This problem uses bundled testdata.

• Subtask 1 (5 pts): $n \le 10$.
• Subtask 2 (5 pts): $S$ is a path.
• Subtask 3 (5 pts): $T$ is a path.
• Subtask 4 (5 pts): $S$ is a star (also called "juhua", 菊花).
• Subtask 5 (10 pts): $S$ and $T$ each have only one diameter, and all nodes with degree $> 2$ exist only on the diameter.
• Subtask 6 (10 pts): The initial diameters of $S$ and $T$ have the same length.
• Subtask 7 (25 pts): $n \le 500$.
• Subtask 8 (35 pts): No special constraints.

For $100\%$ of the data, $1 \le a_i, b_i, c_i, d_i \le n \le 2 \times 10^3$.

When all journeys end, and I fall into sleep.

I will surely return to this summer.

Translated by ChatGPT 5