Computation of a Road Network Plan

Byteman is planning a road trip around Byteland, but he could not get a map of the country. From his friends he learned a few facts about the Bytelandian road network:

• There are $n$ cities in Byteland, numbered from $1$ to $n$.
• Every road is bidirectional and joins two different cities.
• For every pair of different cities there is exactly one path (a sequence of one or more roads on which no city repeats) connecting them.
• The longest such path, measured in roads, uses exactly $d$ roads.

The second and third facts together mean the network is a tree: it is connected and has no cycles, so it has exactly $n - 1$ roads. Here $d$ is the number of roads on the longest path in that tree (its diameter).

Help Byteman reconstruct one road network that is consistent with everything he learned, or determine that no such network exists.

The only line of input contains two integers $n$ and $d$ ($2 \le n \le 200$, $0 \le d < n$), separated by a single space.

If no road network satisfies the conditions, output a single line with the word BRAK (Polish for none). This happens exactly when $d = 0$, or when $d = 1$ and $n \ge 3$ (a tree with at least three cities always has diameter at least $2$).

Otherwise output exactly $n - 1$ lines. Among all valid plans your program must print the following specific one:

1. First print the $d$ roads of the main chain along cities $1, 2, \ldots, d + 1$, one per line and in order: 1 2, then 2 3, and so on up to d d+1.
2. Let $c = \lfloor d / 2 \rfloor + 1$. Then, for each remaining city $j$ from $d + 2$ to $n$ in increasing order, print the road c j, attaching city $j$ directly to city $c$.

Each printed line contains the two distinct city numbers of one bidirectional road, separated by a single space.