← 返回题目列表

Codeforces · 827/B

B. 高负载

中文机器翻译题面 查看原题

阿尔卡迪再次需要你的帮助!这次他决定建立自己的高速互联网交换点。它应该由 n 个节点组成,并通过尽可能少的电线连接成一个网络(一根电线直接连接两个节点)。恰好k个节点应该是退出节点,这意味着它们中的每一个都应该恰好连接到网络的另一个节点,而所有其他节点应该连接到至少两个节点,以增加系统稳定性。

Arkady 希望使系统尽可能快,因此他希望最小化两个出口节点之间的最大距离。两个节点之间的距离是封装在这两个节点之间需要经过的电线数量。

帮助Arkady找到一种构建网络的方法,使两个最远的出口节点之间的距离尽可能小。

输入

第一行包含两个整数 n 和 k (3 ≤ n ≤ 2·105, 2 ≤ k ≤ n - 1) — 节点总数和退出节点数。

请注意,在给定的约束范围内,始终可以构建至少一个具有 n 个节点和 k 个出口节点的网络。

输出

在第一行中打印两个最远出口节点之间的最小可能距离。在接下来的 n - 1 行中,每一行打印两个整数:通过电线连接的节点的 id。每根电线的描述应只打印一次。您可以按任意顺序打印电线和电线末端。节点的编号应从 1 到 n。退出节点可以有任何 id。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

3 2

输出 #1

2
1 2
2 3

输入 #2

5 3

输出 #2

3
1 2
2 3
3 4
3 5

注意

在第一个示例中,唯一的网络显示在左图中。

在第二个示例中,右图显示了最佳网络之一。

退出节点突出显示。