- Practice
- Algorithms
- Graph Theory
- Diameter Minimization

# Diameter Minimization

# Diameter Minimization

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 ).