Build a tree

Time limit2sMemory limit512 MB

Summary

Construct a tree on n nodes with exactly m leaves whose sorted edge list is lexicographically smallest, and print its n-1 edges.

Level: Medium4 of 10
Topics: Tree, Greedy, Implementation, Brute force
Solved: No attempts yet

Problem

You are given $n$ and $m$ . Build a tree that has $n$ nodes and exactly $m$ leaves, then print it.

A tree is a connected graph with no cycle, and a leaf is a node of degree $1$ . The nodes are numbered $0$ through $n-1$ .

Several trees can satisfy the condition. Print the one whose edge list comes first in lexicographic order. Build the edge list this way: write each edge as $u\ v$ with the smaller endpoint first, so $u < v$ , then order the $n-1$ edges by $u$ ascending, breaking ties by $v$ ascending. Compare two edge lists as sequences of $2(n-1)$ integers.

Under the given limits such a tree always exists.

Input

The first line contains $n$ and $m$ , separated by a space. ( $3 \le n \le 50$ , $2 \le m \le n-1$ )

Output

Print the $n-1$ edges of the tree, one per line, in the order defined above. On each line print the two endpoints of the edge, smaller number first, separated by a space.

Examples4

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