Contest Duration: - (local time) (120 minutes) Back to Home
D - Halftree /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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

### 制約

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

### 入力

N K


### 出力

M
a_1 b_1
a_2 b_2
\vdots
a_M b_M


### 入力例 1

5 2


### 出力例 1

2
2 3
2 4


### 入力例 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