AT_abc165_e [ABC165E] Rotation Matching

题目描述

你将要举办一个名为“AtCoder じゃんけん”的一对一游戏比赛。比赛共有 $N$ 名参赛者，每位参赛者被分配了 $1$ 到 $N$ 之间的不同编号。竞技场中有 $M$ 个可以容纳两人的对战场地，你需要为每个对战场地分配两个不同的 $1$ 到 $N$ 之间的整数。不能在多个对战场地分配相同的整数。

比赛由 $N$ 轮组成，每一轮按如下方式进行：

• 每位参赛者，如果有分配给自己的编号的对战场地，就前往该场地，并与到场的另一位参赛者对战。
• 之后，每位参赛者的编号加 $1$。如果加 $1$ 后编号变为 $N+1$，则将其编号改为 $1$。

你希望在 $N$ 轮比赛中，不存在任何参赛者与同一位参赛者对战两次或以上。请输出一种满足上述条件的对战场地编号分配方案。在给定的约束下，保证一定存在这样的分配方案。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$

输出格式

请输出 $M$ 行，每行输出为第 $i$ 个对战场地分配的两个整数。

$a_1$ $b_1$
$a_2$ $b_2$
$\cdots$
$a_M$ $b_M$

输入输出样例 #1

输入 #1

4 1

输出 #1

2 3

输入输出样例 #2

输入 #2

7 3

输出 #2

1 6
2 5
3 4

说明/提示

约束条件

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

样例解释 1

假设有 $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$ 轮比赛中，没有任何参赛者与同一位参赛者对战两次，因此该输出是正确的。

由 ChatGPT 4.1 翻译