分数: 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