Edge-Disjoint Spanning Trees

Time limit2sMemory limit512 MB

Summary

Given N and K, output K edge-disjoint spanning trees of the complete graph on N vertices, or -1 if impossible.

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

Problem

You are given a complete graph with $N$ vertices. Find $K$ spanning trees that are edge-disjoint.

The leftmost figure above shows a complete graph with four vertices. The two figures to the right are two spanning trees of this graph that share no edge.

Input

You are given two integers $N$ and $K$ on a single line ( $2 \le N \le 10^4$ , $1 \le K \le 100$ ).

Output

If there is no tuple of $K$ spanning trees that satisfies the conditions, print $-1$ .

Otherwise, print $K$ spanning trees. Each spanning tree must be printed on $N - 1$ lines. The $i$ -th line must contain two space-separated integers: the two endpoints of the $i$ -th edge. The vertices are numbered $1$ through $N$ . You may print an empty line between consecutive trees.

Examples2

Example 1
Input
```
4 2
```
Expected output
```
1 2
1 4
2 3

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