kreg

The N nodes of an undirected graph are numbered with integers from 1 to N. The degree of a node X of the graph is equal to the number of edges that have one of the two extremities in X. An undirected graph is called K-regular if the degree of each node is equal to K. An undirected graph is called connected if any node can be reached from any another node by traveling only on the graph's edges.

Task

Being given K and N, build an undirected connected and K-regular graph.

Input Data

Input file kreg.in contains on the first line the positive integers K and N, separated by a space.

Output Data

Output file kreg.out will contain N*K/2 lines. Each line corresponds to an edge of the built graph and will contain two integers, A and B, separated by a space, representing the extremities of the edge (1<=A,B<=N, A different from B).

Constraints and Statements

Example
kreg.in kreg.out (a possible solution)

4 6

 1 2
1 6
5 4
6 3
5 1
2 5
5 3
2 6
3 4
1 4
6 4
2 3

Time limit: 0.2 seconds/test


Mugurel Ionut Andreica
Bucharest Polytechnic University, Automatics and Computers Department
mugurel_ionut@yahoo.com