Router 7

Henry and Hetty were recently hired by a networking company from Piatra Neamț. Their first project is to build a new router, the Connect Ethernet Operating Interface 2016, which has the following parts:

• $N$ input nodes, numbered 1 to $N$.
• $N$ output nodes, numbered $N+1$ to $2 \times N$.
• $K$ internal nodes, numbered $2 \times N+1$ to $2 \times N+K$.
• $M$ unidirectional direct connections between pairs of distinct nodes.

Node $X$ can send data to node $Y$ if $X = Y$, or if some node $Z$ exists such that $X$ can send data to $Z$ and there is a direct connection from $Z$ to $Y$.

If $X$ can send data to $Y$ and $X \neq Y$, the 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)\}$ for some $L \ge 2$, with $A_1 = X$ and $A_L = Y$.

A router works properly if:

• Each input node can send data to each output node.
• Each input node can receive data only from itself.
• Each output node can send data only to itself.
• For any two nodes $X \neq Y$, if $X$ can send data to $Y$, then $Y$ cannot send data to $X$.
• For any two nodes $X \neq Y$, if $X$ can send data to $Y$, the data path from $X$ to $Y$ is unique. In particular, any two nodes are connected 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_{2 \times N+K})$.

For the given specification, build a router that:

• has exactly $N$ input nodes and $N$ output nodes;
• uses at most $M_{lim}$ direct connections;
• uses maximum power at most $P_{lim}$;
• uses at most 500000 nodes in total ($N_{tot} = 2 \times N + K \le 500000$).

The first and only line contains three integers: $N$, the number of input and output nodes, $M_{lim}$, the maximum number of direct connections, and $P_{lim}$, the maximum power used by the router.

For this test, $N = 9978$, $M_{lim} = 100000$, and $P_{lim} = 100000$.

Print $N_{tot} = 2 \times N + K$ and $M$ on the first line, separated by a space. Then print $M$ lines, each containing two integers $X$ and $Y$, which means a direct connection from node $X$ to node $Y$ is built.