P7807 Magic Growth

Source: [Eight Immortals Toasting](/paste/78f1vlm0), which you can click. - Lü Dongbin — Drunkenly lifts the pot with immense strength. - Tieguai Li — Spins the elbow and knee, drunk yet real. - Han Zhongli — Stumbles, hugs the jar, and rams the heart. - **Lan Caihe — Lifts a toast with one hand and breaks the waist block**. - Zhang Guolao — Drunkenly throws the cup and kicks in a chain. - Cao Guojiu — The immortal toasts and locks the throat. - Han Xiangzi — Grabs the wrist, strikes the chest, and drunkenly plays the flute. - He Xiangu — Bends the waist to offer wine, drunkenly swaying her steps.

You are given a tree $T$ with $n$ nodes, where the number of nodes connected to any node is at most $2$. Now perform operations on nodes $u = 1 \sim n$ in order: - Randomly choose an integer $x(\ge k)$. - Create $x$ new nodes, and connect each new node to $u$ with an edge. Obviously, after all operations, the result is still a tree $T'$, whose number of nodes is $m = n + \sum x$. Given the resulting tree $T'$ and its number of nodes $m$, reconstruct the original tree $T$. If there are multiple solutions, output **any one** that makes $\color{black}n$ **as large as possible**. Note that during reconstruction and output, we only care about the shape of the tree, not the relative numbering of nodes.

The first line contains two positive integers $m, k$, representing the number of nodes in tree $T'$ and the lower bound of the random number $x$. Lines $2 \sim m$ each contain two positive integers $u, v$, representing an edge in $T'$.

The first line outputs one positive integer $n$, the number of nodes in the constructed tree $T$. Lines $2 \sim n$ each output two positive integers $u, v$, representing an edge in $T$. The output $u, v$ must satisfy: $1 \le u, v \le n$.

#### Sample Explanation In sample $\#1$, only node $1$ can be in tree $T$: its corresponding $x$ is $4$. In sample $\#2$, nodes $1, 2, 3$ are in tree $T$: node $1$ corresponds to $x$ being $4$, and nodes $2, 3$ correspond to $x$ being $0$. In sample $\#3$, nodes $1, 2, 3$ are in tree $T$: their randomly chosen $x$ are all $2$.  Sample $\#3$ provides an illustration. The red nodes represent the nodes in tree $T$, and all nodes in the figure are on $T'$. #### Constraints | Subtask | Score | $x=$ | | :----------: | :----------: | :----------: | | $1$ | $30$ | $0$ | | $2$ | $30$ | $1$ | | $3$ | $40$ | | | $4$ | $0$ | Hack | Note: Subtask 4 is unscored Hack testdata. Only if you pass all subtasks $1 \sim 4$ will it be considered AC. For $100\%$ of the data: $1 \le m \le 10^5, k \in [0, m)$, and the input guarantees that a solution exists. --- ### Afterword Aurora magic flowers are so cute $\sim$  Translated by ChatGPT 5