← 返回题目列表

AtCoder · arc152_d

D. 半树

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

分数: 700 点

问题陈述

我们有一个无向图 N 顶点编号 0 通过 N-1 一开始没有边缘。 您可以根据需要向该图添加边。 添加边完成后,将使用给定整数执行一次以下操作 K.

  • 对于您添加的每条边,令 u 和 v 为其端点,并且将在两个顶点之间添加一条边 (u+K) \mathrm{mod} N 和 (v+K) \mathrm{mod} N。 即使这些顶点之间已经存在一条边,也会添加该边,从而形成多重边。

对于给定的 N 和 K,找到一组应添加的边,以便操作后图将成为一棵树。 如果不存在这样的边集,请指出这一事实。

约束

  • 2\leq N\leq 2\times 10^5
  • 1\leq K\leq N-1
  • 输入中的所有值都是整数。

输入

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

N K

输出

如果有一组满足要求的边,令 M 是边数,并且 a_i 和 b_i 是由 i第一条边,并按以下格式打印解决方案。 这里, 0\leq M\leq N 必须成立,并且所有值都必须是整数。可以以任何顺序打印边缘以及边缘的端点。

M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

如果存在多个解决方案,则将接受其中任何一个。

如果没有一组边满足要求,则打印 -1.


示例输入 1

5 2

示例输出 1

2
2 3
2 4

该操作将添加边缘 4-0 和 4-1。 然后,该图将是一棵树,因此这是合法的输出。


示例输入 2

2 1

示例输出 2

-1

操作后无法再有树。


示例输入 3

7 1

示例输出 3

3
0 1
2 3
4 5