CF827B High Load

Arkady 再次需要你的帮助！这次他决定建立自己的高速互联网交换节点。Arkady 希望用最少数量的电线将 $n$ 个节点连接成一个网络（一根电线直接连接两个节点）。其中有且仅有 $k$ 个节点应为“出口节点”，这意味着每个出口节点只能与网络中的另一个节点相连，其余所有节点则必须至少与两个节点相连，以提高系统的稳定性。 Arkady 希望让系统尽可能快，因此想最小化任意两个出口节点之间的最大距离。这里，两个节点之间的距离指的是从一个节点到另一个节点，信息包经过的电线数。 请你帮 Arkady 设计一个这样的网络，使得所有出口节点中距离最远的两个出口节点之间的距离尽可能小。

第一行包含两个整数 $n$ 和 $k$（$3 \leq n \leq 2 \cdot 10^{5}$，$2 \leq k \leq n-1$），分别表示节点总数和出口节点数。 注意，在给定约束条件下，至少能构造一个包含 $n$ 个节点且有 $k$ 个出口节点的网络。

第一行输出任意两个距离最远的出口节点之间的最小可能距离。接下来 $n-1$ 行，每行输出两个整数，表示一根电线所连接的两个节点的编号。每根电线只需输出一次，顺序不限。节点编号为 $1$ 到 $n$。出口节点可以有任意编号。 如果存在多种最优方案，输出任意一种即可。

在第一个样例中，唯一的网络如左图所示。 在第二个样例中，示例中给出的网络是最优网络之一。 出口节点已标记高亮。  由 ChatGPT 5 翻译