Router 6

Henry and Hetty were hired by a networking company, and their first project is a router, the Connect Ethernet Operating Interface 2016. A router is made of:

• $N$ input nodes, numbered $1$ to $N$,
• $N$ output nodes, numbered $N+1$ to $2N$,
• $K$ internal nodes, numbered $2N+1$ to $2N+K$,
• $M$ unidirectional direct connections, each one between two distinct nodes.

A node $X$ can send data to a node $Y$, which is the same as saying $Y$ can receive data from $X$, when $X = Y$, or when some node $Z$ exists such that $X$ can send data to $Z$ and there is a direct connection from $Z$ to $Y$.

When $X$ can send data to $Y$ and $X \neq Y$, a data path from $X$ to $Y$ is a set of direct connections $\{(A_1, A_2), (A_2, A_3), \ldots, (A_{L-1}, A_L)\}$ with $L \geq 2$, $A_1 = X$ and $A_L = Y$.

The router works properly when all five conditions hold:

• every input node can send data to every output node,
• every input node can receive data only from itself,
• every output node can send data only to itself,
• for two nodes $X \neq Y$, if $X$ can send data to $Y$ then $Y$ cannot send data to $X$,
• for two nodes $X \neq Y$, if $X$ can send data to $Y$ then the data path from $X$ to $Y$ is unique. In particular, two nodes are joined by at most one direct connection.

The power needed to operate node $X$ is $P_X = IN_X \times OUT_X$, where $IN_X$ is the number of input nodes that can send data to $X$, and $OUT_X$ is the number of output nodes that can receive data from $X$. The maximum power used by the router is $P_{max} = \max(P_1, P_2, \ldots, P_{2N+K})$.

Build a router that works properly, has exactly $N$ input nodes and exactly $N$ output nodes, uses at most $M_{lim}$ direct connections, has $P_{max} \le P_{lim}$, and uses at most $500\,000$ nodes in total, so $N_{tot} = 2N + K \le 500\,000$.

Many routers stay inside those limits, so the output section fixes one of them. Print that router.

One line holds three integers $N$, $M_{lim}$ and $P_{lim}$: the number of input nodes, which equals the number of output nodes, the largest number of direct connections allowed, and the largest power allowed.

$1 \le N \le 10\,000$, $1 \le M_{lim} \le 500\,000$, $N \le P_{lim} \le 1\,000\,000$. Every input node $X$ has $IN_X = 1$ and $OUT_X = N$, so an answer exists only when $P_{lim} \ge N$.

In every test case the router described in the output section uses at most $M_{lim}$ direct connections.

Print the router built by the rules below. It works properly and its maximum power is at most $P_{lim}$.

Let

$g = \min\left(N, \left\lfloor \frac{P_{lim}}{N} \right\rfloor\right), \qquad c = \left\lfloor \sqrt{P_{lim}} \right\rfloor, \qquad b = \left\lfloor \frac{c}{g} \right\rfloor.$

Cut the input nodes into $S = \lceil N / g \rceil$ groups of $g$ consecutive nodes. Input group $j$ holds the input nodes $(j-1)g+1$ to $\min(jg, N)$, so the last group can be smaller than the others. Cut the output nodes the same way: output group $j$ holds the output nodes $N + (j-1)g + 1$ to $N + \min(jg, N)$.

Cut the group indices $1$ to $S$ into $B = \lceil S / b \rceil$ blocks of $b$ consecutive indices. Block $k$ holds the group indices $(k-1)b+1$ to $\min(kb, S)$, so group $j$ lies in block $\lfloor (j-1)/b \rfloor + 1$. The input side and the output side use the same blocks.

There are $K = 2S + B^2$ internal nodes, numbered in this order:

• one collector node per input group: node $2N + j$ belongs to input group $j$,
• one hub node per pair of blocks: node $2N + S + (k-1)B + l$ belongs to the pair (input block $k$, output block $l$),
• one distributor node per output group: node $2N + S + B^2 + j$ belongs to output group $j$.

The direct connections, in the order they must be printed:

1. for each input group $j$ in increasing order, and each input node $x$ of that group in increasing order, a connection from $x$ to the collector node of group $j$,
2. for each input group $j$ in increasing order, and each output block $l$ in increasing order, a connection from the collector node of group $j$ to the hub node of the pair (block of group $j$, block $l$),
3. for each output group $j$ in increasing order, and each input block $k$ in increasing order, a connection from the hub node of the pair (block $k$, block of group $j$) to the distributor node of group $j$,
4. for each output group $j$ in increasing order, and each output node $y$ of that group in increasing order, a connection from the distributor node of group $j$ to $y$.

That router has $N_{tot} = 2N + 2S + B^2$ and $M = 2N + 2SB$.

On the first line print $N_{tot}$ and $M$, separated by a space. On each of the next $M$ lines print two integers $X$ and $Y$, separated by a space, meaning a direct connection runs from node $X$ to node $Y$. Keep the order given above.