Sliding Tree

The trick is that this is secretly a diameter problem. The degrees are bait. Pretty convincing bait, but still bait.

Key Observation

A path graph with $n$ vertices has diameter $n-1$.

So if the current tree has diameter $d$, then any final path must somehow grow the diameter from $d$ to $n-1$.

Now look at one sliding operation $(a,b,c)$.

The only local structure that changes is around $b$:

• $a$ stays connected to $b$,
• $c$ stays connected to $b$,
• every other neighbor of $b$ gets moved from $b$ to $c$.

For any two vertices, their old path either does not care about this local change, or it passes through $b$. If it passes through $b$, the distance changes by at most $1$:

• going between the $a$-side and some moved side gets $1$ longer,
• going between the $c$-side and some moved side gets $1$ shorter,
• going between two moved sides stays the same,
• going between $a$ and $c$ stays the same.

So one operation increases the diameter by at most $1$.

Therefore, if the original diameter is $d$, we need at least

$(n-1)-d$

operations. No way around it. The diameter is the receipt.

Can We Always Hit This Lower Bound?

Yes.

Take a diameter path from endpoint $x$ to endpoint $y$, and root the tree at $x$.

If the tree is already a path, this diameter contains all vertices, and $d=n-1$.

Otherwise, some vertex is not on this diameter path. Since the tree is connected, there is an edge $(u,v)$ such that:

• $u$ is on the diameter,
• $v$ is not on the diameter.

Also, $u$ cannot be the root endpoint $x$. If $x$ had a neighbor outside the diameter, then that outside vertex would be even farther from $y$ than $x$ is, which contradicts the diameter. Same logic rules out the other endpoint too.

Let $a$ be the parent of $u$ in the rooted tree. So $a$ is the previous vertex on the diameter path toward $x$.

Now perform the operation:

$(a,u,v).$

What happens?

The next diameter neighbor of $u$ toward $y$ gets moved from $u$ to $v$. So the old diameter path

$x \dots a-u-w \dots y$

turns into

$x \dots a-u-v-w \dots y.$

That path is exactly one edge longer.

So the diameter increases by at least $1$. From the earlier observation, it cannot increase by more than $1$. Therefore it increases by exactly $1$.

This means we can repeat this idea until the diameter becomes $n-1$, using exactly $(n-1)-d$ operations, which matches the lower bound. Optimal, clean, no DP circus needed.

What We Need To Output

We only need the first operation.

Algorithm:

1. Find one endpoint $x$ of a diameter by BFS/DFS from any vertex.
2. Find the opposite endpoint $y$ by BFS/DFS from $x$, also storing parents.
3. If $\operatorname{dist}(x,y)=n-1$, print $-1$.
4. Mark all vertices on the diameter path from $y$ back to $x$.
5. Find an edge $(u,v)$ where $u$ is marked and $v$ is not.
6. Print parent[u] u v.

That operation is guaranteed to be the first move of an optimal sequence.