Rotation Matching

题目描述

你将要举办一场一对一的游戏比赛，称为 AtCoder Janken。(Janken 是石头剪刀布的日语名称。) $N$ 名选手将参加这场比赛，他们被赋予从 $1$ 到 $N$ 的不同整数。 竞技场有 $M$ 个供两名选手对战的场地。你需要为每个场地分配两个介于 $1$ 和 $N$（含）之间的不同整数。 你不能把同一个整数分配到多个场地。 比赛由 $N$ 轮组成，每一轮按如下方式进行：

对于每个选手，如果存在一个场地被分配了该选手的整数，则该选手前往该场地并与来该场地的另一名选手对战。 然后，每名选手的整数加 $1$。如果变为 $N+1$，则改为 $1$。

你要确保在这 $N$ 轮中没有任何一名选手与同一对手对战超过一次。 打印满足该条件的场地整数分配。 可以证明，在给定的约束下总是存在这样的分配。

输入格式

输入采用标准输入，格式如下： $N$ $M$

输出格式

打印 $M$ 行，格式如下。 第 $i$ 行应包含分配给第 $i$ 个场地的两个整数 $a_i$ 和 $b_i$。 $a_1$ $b_1$ $a_2$ $b_2$ : $a_M$ $b_M$

4 1

2 3

7 3

1 6
2 5
3 4

提示

$1 \leq M$ $M \times 2 +1 \leq N \leq 200000$我们把四名选手称为 A、B、C 和 D，假设他们最初被分配的整数分别为 $1$、$2$、$3$ 和 $4$。

第 $1$ 轮由 B 和 C 对战，他们的整数分别是 $2$ 和 $3$。这一轮结束后，A、B、C 和 D 的整数变为 $2$、$3$、$4$ 和 $1$。

第 $2$ 轮由 A 和 B 对战，他们的整数分别是 $2$ 和 $3$。这一轮结束后，A、B、C 和 D 的整数变为 $3$、$4$、$1$ 和 $2$。

第 $3$ 轮由 D 和 A 对战，他们的整数分别是 $2$ 和 $3$。这一轮结束后，A、B、C 和 D 的整数变为 $4$、$1$、$2$ 和 $3$。

第 $4$ 轮由 C 和 D 对战，他们的整数分别是 $2$ 和 $3$。这一轮结束后，A、B、C 和 D 的整数变为 $1$、$2$、$3$ 和 $4$。

在四轮中没有选手与同一对手对战超过一次，因此该解将被接受。

标签: AtCoder|abc165E

来源

AtCoder|abc165E