轮转匹配

题目描述

你要主办一个名为「AtCoder 猜拳」的一对一游戏大会。 大会共有 $N$ 名参赛者,每人被分配了 $1$ 到 $N$ 中互不相同的编号。 竞技场中准备了 $M$ 个可容纳两人的对战台,你必须给每个对战台分配两个 $1$ 以上 $N$ 以下互不相同的整数。 不能给多个对战台分配相同的整数。 大会由 $N$ 轮构成,每轮按如下方式进行:

• 每名参赛者如果存在分配了自己编号的对战台,就去那里,与来到该对战台的另一方对战。

• 之后,每名参赛者将自己的编号加 $1$。如果加 $1$ 后的编号为 $N+1$,则将该值改为 $1$。

你希望在整个 $N$ 轮中,不存在与同一名参赛者对战两次以上的参赛者。 请输出一个满足上述条件的对战台整数分配方案。 可以证明,在给定约束下这样的分配方案必然存在。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$

输出格式

按以下格式输出 $M$ 行。 第 $i$ 行输出分配给第 $i$ 个对战台的两个整数。

$a_1$ $b_1$
$a_2$ $b_2$
$:$
$a_M$ $b_M$

样例

4 1

2 3

将 $4$ 名参赛者记为 $A,B,C,D$,假设最初 $A$ 分配 $1$、B 分配 $2$、C 分配 $3$、D 分配 $4$。

• 第 $1$ 轮中,分配了 $2$ 的 B 与分配了 $3$ 的 C 对战,之后 A 的编号变为 $2$、B 的编号变为 $3$、C 的编号变为 $4$、D 的编号变为 $1$。

• 第 $2$ 轮中,分配了 $2$ 的 A 与分配了 $3$ 的 B 对战,之后 A 的编号变为 $3$、B 的编号变为 $4$、C 的编号变为 $1$、D 的编号变为 $2$。

• 第 $3$ 轮中,分配了 $2$ 的 D 与分配了 $3$ 的 A 对战,之后 A 的编号变为 $4$、B 的编号变为 $1$、C 的编号变为 $2$、D 的编号变为 $3$。

• 第 $4$ 轮中,分配了 $2$ 的 C 与分配了 $3$ 的 D 对战,之后 A 的编号变为 $1$、B 的编号变为 $2$、C 的编号变为 $3$、D 的编号变为 $4$。

由于在整个 $4$ 轮中不存在与同一名参赛者对战两次以上的参赛者,所以这个输出是正确的。

7 3

1 6
2 5
3 4

数据范围

• $1 \leq M$
• $M \times 2 +1 \leq N \leq 200000$

提示

答案不唯一,输出任意合法解即可。