Bus Lines

Time limit1sMemory limit512 MB

Summary

Build a connected graph on vertices 1..n with m edges whose endpoint sums are all distinct, or report that this is impossible.

Level: Medium6 of 10
Topics: Graph, Greedy, Implementation, Math
Solved: No attempts yet

Problem

After many years without any public transport, the town Krockholm will finally get a network of bus lines. The plans are still on the drawing board, but it has been decided that there shall be $n$ stations labelled $1$ to $n$ , and $m$ bus lines where each line connects two stations. The only thing remaining is to decide which pairs of stations should be connected. One important requirement is that it should be possible to get from any station to any other. In addition to this, someone had the brilliant idea that the bus lines should be labelled by the sum of their endpoints. This means that all of these sums must be different.

You are given two integers $n$ and $m$ . Construct a graph with $m$ edges and $n$ vertices labelled $1$ to $n$ , such that:

The graph is connected.
The sums of edge endpoints are distinct.

Input

The input consists of a single line containing two integers $n$ and $m$ ( $2 \leq n \leq 100$ , $1 \leq m \leq 10^4$ ).

Output

If it is not possible to construct a graph with the given properties, print "-1". Otherwise, print $m$ lines where the $i$ 'th line contains two integers $a\_i$ , $b\_i$ , the endpoints of the $i$ 'th edge. If there are many possible solutions, any one of them will be accepted.

Examples3

Example 1
Input
```
4 4
```
Expected output
```
2 1
2 3
4 3
4 2
```
Example 2
Input
```
10 100
```
Expected output
```
-1
```
Example 3
Input
```
10 1
```
Expected output
```
-1
```