配点 : $700$ 点

問題文

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

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

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

制約

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

入力

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

$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 と出力せよ。

5 2

2
2 3
2 4

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

2 1

-1

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

7 1

3
0 1
2 3
4 5