30292번 - Simple Link Cut Problem 스페셜 저지다국어

You are given a tree with $N$ vertices. You can repeat the following operation at most $10^5$ times.

• Choose four distinct vertices $v_1, v_2, v_3, v_4$ such that there exist edges between $v_1$ and $v_2$, $v_2$ and $v_3$, $v_3$ and $v_4$. Remove these edges and add edges between $v_1$ and $v_3$, $v_1$ and $v_4$, $v_2$ and $v_4$.

Your task is transform the given tree so that its diameter is at most $3$. Find a sequence of operations that does so.

The first line contains one integer $N$.

The $i$-th of the following $N-1$ lines contains space-separated two integers $x_i$ and $y_i$, meaning that the $i$-th edge connects vertices $x_i$ and $y_i$ in the tree.

At the first line, print $K$, the number of operations.

In the next $K$ line, print four integers $v_1$, $v_2$, $v_3$, $v_4$ separated by space.

If there are multiple solutions, print any. It can be proven that there exists at least one way to achieve the goal.

Note that you do not have to minimize $K$.

• $4 \leq N \leq 100$
• $1 \le x_i, y_i \le N$; $x_i \neq y_i$ $(1 \le i \le N-1)$
• It is guaranteed that the given edges form a tree.
• $0 \leq K \leq 100,000$
• $v_1, v_2, v_3, v_4$ should satisfy the conditions of the given operation.

The distance between two vertices $u$ and $v$ is defined as the number of the edges of the unique path from $u$ to $v$.

The diameter of a tree is the maximum distance between any two vertices.