题目背景

Source：八仙敬酒，这是可以点的。

• 吕洞宾——醉酒提壶力千钧；
• 铁拐李——旋肘膝撞醉还真；
• 汉钟离——跌步抱坛兜心顶；
• 蓝采和——单提敬酒拦腰破；
• 张果老——醉酒抛杯踢连环；
• 曹国舅——仙人敬酒锁喉扣；
• 韩湘子——擒腕击胸醉吹箫；
• 何仙姑——弹腰献酒醉荡步。

题目描述

现有一个 $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$。

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

提示

样例说明

样例 $\#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$		$1$
$3$	$40$
$4$	$0$	Hack

说明：Subtask4 为不计分 Hack 数据，只有通过全部的 Subtask $1\sim4$ 才算 AC。

对于 $100\%$ 的数据：$1\le m\le10^5,k\in[0,m)$，数据输入保证有解。

---

后记

极光魔花好可爱 $\sim$