正当计算鸡们还沉浸在过年的气氛中时，计算鸡村拉响了警报：远方来了一群程序猿。“他们又要来了！” 全村上下陷入了惊恐。

看过了有手撕鬼子情节的抗日神剧的直径拆除鸡不禁开起了脑洞。作为一种神奇的生物，每个程序猿都长得十分古怪。人的身体形状可以抽象为一个五角星型的 $6$ 个结点的树，而程序猿则可以长成任意一个 $n$ 个结点的树。那么，如果每次能拆除这棵树的直径，最多要花费多少时间才能把这棵树全部删除呢？

具体来说，直径拆除鸡脑补的是这样一个算法：

• 输入一棵 $n$ 个结点的树，该算法进行过程中保证每时每刻保证图是一个森林
• 令 $S = 0$，重复如下过程直到所有结点均被删除
  • 从图中任意找一个连通块，显然该连通块肯定是一棵树
  • 假设该树有 $t$ 个结点，执行 $S = S + t$
  • 从该树中找一条最长简单路，假设是从 $a$ 到 $b$。如果有多条那么选择 $a$ 最小的，当 $a$ 一样时选择 $b$ 最小的
  • 删除从 $a$ 到 $b$ 的简单路上的所有结点，包括 $a$ 和 $b$，这将导致该树结点会被删光或者分裂成一个或多个更小的树

计算次数即最后 $S$ 所存储的值。

现在，给你 $n, m$，请你构造一个包含 $n$ 个结点的树，且计算次数至少为 $m$，输入数据保证有解。

输入格式

一行，两个整数 $n, m$。保证 $n \ge 1, m \ge 0$。

输出格式

$n - 1$ 行，每行两个整数 $v, u$ 表示树上一条从 $v$ 到 $u$ 的边，需要满足 $1 \le v, u \le n$。

样例一

input

4 5

output

1 2
1 3
1 4

explanation

输出了一个包含 $(1, 2), (1, 3), (1, 4)$ 三条边的四个结点的树。第一次直径拆除鸡将删除从 $2$ 到 $3$ 的简单路径上的所有结点，即 $\{2, 1, 3\}$，删除后仅剩一个结点，再花费 $1$ 的计算次数将其删除。总共 $S = 4 + 1 = 5$。

另外还有一种四个结点的方案，边分别是 $(1, 2), (2, 3), (3, 4)$。这棵树的最长简单路为 $\{1, 2, 3, 4\}$，所以第一次删除后所有结点均会被删除，总计算次数为 $4$，无法满足 $S \ge m$ 的条件。

样例二

input

12 0

output

1 2
2 3
1 4
4 5
1 7
6 7
7 8
1 10
10 9
10 11
10 12

限制与约定

对于所有数据，保证 $0 \le m \le 10^9$ 且保证有解。

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载