We define the diameter of a strongly-connected oriented graph, , as the minimum integer such that for each there is a path from to of length (recall that a path's length is its number of edges).
Given two integers, and , build a strongly-connected oriented graph with vertices where each vertex has outdegree and the graph's diameter is as small as possible (see the Scoring section below for more detail). Then print the graph according to the Output Format specified below.
Here's a sample strongly-connected oriented graph with nodes, whose outdegree is and diameter is .
Note: Cycles and multiple edges between vertices are allowed.
Input Format
Two space-separated integers describing the respective values of (the number of vertices) and (the outdegree of each vertex).
Constraints
Scoring
We denote the diameter of your graph as and the diameter of the graph in the author's solution as . Your score for each test case (as a real number from to ) is:
- if
- if
- if
Output Format
First, print an integer denoting the diameter of your graph on a new line.
Next, print lines where each line () contains space-separated integers in the inclusive range from to describing the endpoints for each of vertex 's outbound edges.
Sample Input 0
5 2
Sample Output 0
2
1 4
2 0
3 1
4 2
0 3
Explanation 0
The diagram below depicts a strongly-connected oriented graph with nodes where each node has an outdegree of :
The diameter of this graph is , which is minimal as the outdegree of each node must be . We cannot construct a graph with a smaller diameter of because it requires an outbound edge from each vertex to each other vertex in the graph (so the outdegree of that graph would be ).