← 返回题目列表

AtCoder · abc165_e

E. 旋转匹配

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

您将举办一场名为 AtCoder Janken 的一对一游戏竞赛。 (Janken 是石头剪刀布的日语名称。) N 玩家将参加本次比赛,他们将获得不同的整数 1 通过 N。 竞技场有 M 两名玩家的比赛场地。您需要为每个比赛场地分配两个不同的整数 1 和 N (含)。 您不能将相同的整数分配给多个比赛场地。 比赛由 N 轮,每轮的收益如下:

  • 对于每个玩家,如果有一个分配了该玩家整数的比赛场地,则该玩家将前往该场地并与到达那里的其他玩家战斗。
  • 然后,每个玩家添加 1 为其整数。如果变成 N+1,将其更改为 1.

您想要确保没有玩家在比赛期间与同一对手战斗超过一次 N 回合。 打印满足此条件的整数分配给比赛场地。 可以证明,在给定的约束条件下,这样的分配总是存在的。

约束

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

输入

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

N M

输出

打印 M 行的格式如下。 的 i- 第行应包含两个整数 a_i 和 b_i 分配给 i- 第一个比赛场地。

a_1 b_1
a_2 b_2
:
a_M b_M

示例输入 1

4 1

示例输出 1

2 3

让我们将四个玩家称为 A、B、C 和 D,并假设他们最初被赋予整数 1, 2, 3,和 4。

  • 的 1-st 回合由 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。

在四轮比赛中,没有玩家与同一对手战斗超过一次,因此该解决方案将被接受。


示例输入 2

7 3

示例输出 2

1 6
2 5
3 4