P7807 魔力滋生

Source：[八仙敬酒](/paste/78f1vlm0)，这是可以点的。 - 吕洞宾——醉酒提壶力千钧； - 铁拐李——旋肘膝撞醉还真； - 汉钟离——跌步抱坛兜心顶； - **蓝采和——单提敬酒拦腰破**； - 张果老——醉酒抛杯踢连环； - 曹国舅——仙人敬酒锁喉扣； - 韩湘子——擒腕击胸醉吹箫； - 何仙姑——弹腰献酒醉荡步。

现有一个 $n$ 个点的树 $T$，满足任意一个结点的所连接的结点个数不超过 $2$。 现在依次对结点 $u=1\sim n$ 进行操作： - 随机一个整数 $x(\ge k)$； - 新建 $x$ 个结点，每个结点与 $u$ 之间连一条边。 显然操作完成后仍是一棵树 $T'$，其结点数为 $m=n+\sum x$。 已知操作后的树 $T'$ 及其结点数 $m$，请还原原树 $T$，若有多种方案，输出 **任意一组** 使得 $\color{black}n$ **最大** 的。 值得注意的是，我们进行还原和输出时，只关心树的形状，而不关心结点的相对编号。

第一行输入两个正整数 $m,k$，表示树 $T'$ 的结点数、随机数 $x$ 的下限。 第 $2\sim m$ 行，每行输入两个正整数 $u,v$，表示树 $T'$ 中的一条边。

第一行输出一个正整数 $n$，表示构造出树 $T$ 的结点数。 第 $2\sim n$ 行，每行输出两个正整数 $u,v$，表示树 $T$ 中的一条边。 输出的 $u,v$ 必须满足：$1\le u,v\le n$。

#### 样例说明 样例 $\#1$ 中，只有结点 $1$ 可能在树 $T$ 中：它对应的 $x$ 是 $4$。 样例 $\#2$ 中，结点 $1,2,3$ 在树 $T$ 中：结点 $1$ 对应的 $x$ 是 $4$，结点 $2,3$ 对应的 $x$ 是 $0$。 样例 $\#3$ 中，结点 $1,2,3$ 在树 $T$ 中：它们随机的 $x$ 均为 $2$。  样例 $\#3$ 给出一张示意图，图中红色结点表示树 $T$ 中的结点，图中所有结点都在树 $T'$ 上。 #### 数据范围 | Subtask | Score | $x=$ | | :----------: | :----------: | :----------: | | $1$ | $30$ | $0$ | | $2$ | $30$ | $1$ | | $3$ | $40$ | | | $4$ | $0$ | Hack | 说明：Subtask4 为不计分 Hack 数据，只有通过全部的 Subtask $1\sim4$ 才算 AC。 对于 $100\%$ 的数据：$1\le m\le10^5,k\in[0,m)$，数据输入保证有解。 --- ### 后记 极光魔花好可爱 $\sim$