Problem E
Bus Lines
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.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 4 |
2 1 2 3 4 3 4 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 100 |
-1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 1 |
-1 |
