D - Halftree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 と出力せよ。

入力例 1

5 2

出力例 1

2
2 3
2 4

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

入力例 2

2 1

出力例 2

-1

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

入力例 3

7 1

出力例 3

3
0 1
2 3
4 5

Score : 700 points

Problem Statement

We have an undirected graph with N vertices numbered 0 through N-1 and no edges at first. You may add edges to this graph as you like. When you are done with adding edges, the following operation will be performed once using a given integer K.

  • For each edge you have added, let u and v be its endpoints, and an edge will be added between two vertices (u+K) \mathrm{mod} N and (v+K) \mathrm{mod} N. This edge will be added even if there is already an edge between these vertices, resulting in multi-edges.

For the given N and K, find a set of edges that you should add so that the graph will be a tree after the operation. If there is no such set of edges, indicate that fact.

Constraints

  • 2\leq N\leq 2\times 10^5
  • 1\leq K\leq N-1
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N K

Output

If there is a set of edges that satisfies the requirement, let M be the number of edges, and a_i and b_i be the two vertices connected by the i-th edge, and print a solution in the following format. Here, 0\leq M\leq N must hold, and all values must be integers. The edges may be printed in any order, as well as the endpoints of an edge.

M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

If multiple solutions exist, any of them will be accepted.

If no set of edges satisfies the requirement, print -1.

Sample Input 1

5 2

Sample Output 1

2
2 3
2 4

The operation will add the edges 4-0 and 4-1. Then, the graph will be a tree, so this is a legitimate output.

Sample Input 2

2 1

Sample Output 2

-1

There is no way to have a tree after the operation.

Sample Input 3

7 1

Sample Output 3

3
0 1
2 3
4 5