题目描述

頂点に $0$ から $N-1$ までの番号がついた $N$ 頂点の無向グラフがあり、はじめ、辺はありません。 このグラフに、あなたは好きなように辺を追加することができます。 そして、あなたが辺をすべて追加し終えた後に、与えられる $K$ を用いて以下の操作がちょうど $1$ 回行われます。

• あなたが追加した各辺について、両端の頂点を $u,v$ とするとき、 $2$ 頂点 $(u+K)$ $\mathrm{mod}$ $N$ と $(v+K)$ $\mathrm{mod}$ $N$ の間に辺が追加される。 ただし、この $2$ 頂点間にもともと辺が存在する場合も新しく辺が追加されるため、その場合は操作後には多重辺となる。

与えられた $N,K$ に対して、操作後のグラフが木となるようにするとき、あなたが追加するべき辺の組を求めてください。 そのような辺の組が存在しない場合はそのことを指摘してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$

输出格式

題意を満たす辺の組が存在する場合、辺の数を $M$、 $i$ 番目の辺が結ぶ $2$ 頂点を $a_i,b_i$ として、以下の形式で出力せよ。 ただし、 $0\leq\ M\leq\ N$ でなければならず、全て整数で出力せよ。出力される辺や頂点の順序は問わない。

$M$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_M$ $b_M$

解が複数存在する場合、どれを出力しても正解とみなされる。

題意を満たす辺の組が存在しない場合、-1 と出力せよ。

题目大意

有 $n$ 个点 $0,1,2 ... n-1$ 和一个参数 $k$，你需要连接若干条无向边， 使得将这些点连成一棵树，连边规则如下：

• 选择 $u,v$ 两点，同时连接点 $u$ 和 $v$，点 $(u+k)\mod n$ 和 $(v+k)\mod n$

注意可能存在重边，这时重边算作多条边。

求一个合法的构造方案或输出无解。

数据范围：$1 \le n \le 2 \times 10^5,1 \le k \le n-1$ 且 $n,k \in Z$

5 2

2
2 3
2 4

2 1

-1

7 1

3
0 1
2 3
4 5

提示

制約

• $2\leq\ N\leq\ 2\times\ 10^5$
• $1\leq\ K\leq\ N-1$
• 入力される値はすべて整数である

Sample Explanation 1

操作を行うと、辺 $4$-$0$ と $4$-$1$ が追加されます。 したがって、木が生成されますので、これは正当な出力の $1$ つとなります。

Sample Explanation 2

操作後のグラフが木となるような方法が存在しません。