阿尔卡迪再次需要你的帮助!这次他决定建立自己的高速互联网交换点。它应该由 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
注意
在第一个示例中,唯一的网络显示在左图中。
在第二个示例中,右图显示了最佳网络之一。
退出节点突出显示。