Background

Source: Eight Immortals Toasting, 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.

Problem Description

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.

Input Format

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'$.

Output Format

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$.

5 1
1 2
1 3
1 4
1 5

1

7 0
1 2
1 3
1 4
1 5
1 6
1 7

3
1 2
1 3

9 1
1 2
2 3
1 4
1 5
2 6
2 7
3 8
3 9

3
1 2
2 3

Hint

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

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