English
Zadanie Wyznaczanie planu sieci drogowej (wyz)
Computation of a Road Network Plan
Memory limit: 64 MB
Byteman is going for a car trip around Byteland, but he is unfortunately unable to buy a map of the country. From his friends he learned about some properties of the bytean road network:
- There are
cities in Byteland, numbered from 
to 
.
- Each road is bidirectional and connects two different cities.
- Each pair of different cities is connected by exactly one path, consisting of one ore more roads, on which no city appears more than once.
- The longest path, on which no city appears more than once,
consists of
roads.
Task
Write a program that:
- reads numbers
and 
from the standard input,
- computes any road network plan that is consistent with information collected by Byteman, or checks that no such plan exists,
- writes the result to the standard output.
Input
The first and only line of input contains two integers 
and 
(
, 
), separated with a single space.
Output
If no road network plan exists for the values of parameters 
and 
from
the input, the first and only line of output should contain a single
word BRAK (i.e. none in Polish).
In the opposite case the output should consist of 
lines.
Each line should contain a description of one bidirectional road -
two different integers in the range from 
to 
, separated with
a single space and denoting the numbers of cities connected by this road.
The order of roads and numbers of cities connected by roads in the output
can be arbitrary.
Example
For the input data:
6 3
the correct result is:
1 3 2 3 3 4 4 5 4 6
Task author: Jakub Radoszewski.