Contest Duration: - (local time) (100 minutes) Back to Home
E - Friendships /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• グラフは単純かつ連結である。
• 各頂点には 1, 2, ..., N の番号が付けられている。
• グラフの辺数を M としたとき、各辺には 1, 2, ..., M の番号が付けられていて、辺 i は頂点 u_i と頂点 v_i をつなぐ長さ 1 の辺である。
• 最短距離が 2 であるような頂点対 (i,\ j)\ (i < j) が、ちょうど K 個存在する。

### 制約

• 入力は全て整数である。
• 2 \leq N \leq 100
• 0 \leq K \leq \frac{N(N - 1)}{2}

N K

M
u_1 v_1
:
u_M v_M

5 3

### 出力例 1

5
4 3
1 2
3 1
4 5
2 3

このグラフには最短距離が 2 であるような頂点対が (1,\ 4),\ (2,\ 4),\ (3,\ 5)3 個存在します。よって条件を満たしています。

5 8

### 出力例 2

-1

Score: 500 points

### Problem Statement

Does there exist an undirected graph with N vertices satisfying the following conditions?

• The graph is simple and connected.
• The vertices are numbered 1, 2, ..., N.
• Let M be the number of edges in the graph. The edges are numbered 1, 2, ..., M, the length of each edge is 1, and Edge i connects Vertex u_i and Vertex v_i.
• There are exactly K pairs of vertices (i,\ j)\ (i < j) such that the shortest distance between them is 2.

If there exists such a graph, construct an example.

### Constraints

• All values in input are integers.
• 2 \leq N \leq 100
• 0 \leq K \leq \frac{N(N - 1)}{2}

### Input

Input is given from Standard Input in the following format:

N K

### Output

If there does not exist an undirected graph with N vertices satisfying the conditions, print -1.

If there exists such a graph, print an example in the following format (refer to Problem Statement for what the symbols stand for):

M
u_1 v_1
:
u_M v_M

If there exist multiple graphs satisfying the conditions, any of them will be accepted.

5 3

### Sample Output 1

5
4 3
1 2
3 1
4 5
2 3

This graph has three pairs of vertices such that the shortest distance between them is 2: (1,\ 4), (2,\ 4), and (3,\ 5). Thus, the condition is satisfied.

5 8

### Sample Output 2

-1

There is no graph satisfying the conditions.