Two Stage Router

Problem

A router is built from nodes and one way connections between pairs of distinct nodes:

$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$ one way connections.

Node $X$ can send data to node $Y$ if $X = Y$ , or if there is a node $Z$ such that $X$ can send data to $Z$ and a connection runs from $Z$ to $Y$ . When $X \ne Y$ and $X$ can send data to $Y$ , a data path from $X$ to $Y$ is a set of connections $\{(A_1, A_2), (A_2, A_3), \dots, (A_{L-1}, A_L)\}$ with $L \ge 2$ , $A_1 = X$ and $A_L = Y$ .

The router works properly when all of these hold:

every input node can send data to every output node;
an input node receives data only from itself;
an output node sends data only to itself;
if $X \ne Y$ and $X$ can send data to $Y$ , then $Y$ cannot send data to $X$ ;
if $X \ne Y$ and $X$ can send data to $Y$ , then the data path from $X$ to $Y$ is unique. In particular at most one connection joins any two nodes.

The power of node $X$ is $P_X = \mathrm{IN}_X \times \mathrm{OUT}_X$ , where $\mathrm{IN}_X$ is the number of input nodes that can send data to $X$ and $\mathrm{OUT}_X$ is the number of output nodes that can receive data from $X$ . The maximum power of the router is $P_{max} = \max(P_1, P_2, \dots, P_{2N+K})$ .

You are given $N$ , $M_{lim}$ and $P_{lim}$ . Build the router described in the output section. That router works properly, uses at most $M_{lim}$ connections, keeps $P_{max}$ at most $P_{lim}$ , and uses at most 500000 nodes in total.

Input

One line with three integers $N$ , $M_{lim}$ and $P_{lim}$ , separated by spaces ( $1 \le N \le 5000$ , $N \le P_{lim} \le 10^9$ , $1 \le M_{lim} \le 500000$ ).

The router described in the output section uses at most $M_{lim}$ connections.

Output

Let $s = \min(N, \lfloor P_{lim} / N \rfloor)$ and $g = \lceil N / s \rceil$ . Build the router this way.

Split the input nodes into $g$ groups of $s$ consecutive nodes: input node $i$ belongs to group $\lceil i / s \rceil$ . The last group can hold fewer than $s$ nodes.
Split the output nodes the same way: output node $N + j$ belongs to group $\lceil j / s \rceil$ .
Add $g$ collector nodes. The collector of group $c$ is node $2N + c$ .
Add $g$ distributor nodes. The distributor of group $d$ is node $2N + g + d$ .
Connect every input node to the collector of its own group.
Connect every collector to every distributor.
For every group, connect its distributor to each output node of that group.

On the first line print the total number of nodes $N_{tot} = 2N + 2g$ and the number of connections $M = 2N + g^2$ , separated by a space. On each of the next $M$ lines print two integers $X$ and $Y$ , meaning a connection from node $X$ to node $Y$ . Sort the connections by $X$ in increasing order, and by $Y$ in increasing order when $X$ is equal.