Router 2

Henry and Hetty were hired by a networking company. Their first project is a new router, the Connect Ethernet Operating Interface 2016, built from:

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

A node $X$ can send data to a node $Y$ (equivalently, $Y$ can receive data from $X$) if one of the following holds:

• $X = Y$;
• there is a node $Z$ such that $X$ can send data to $Z$ and a direct connection runs from $Z$ to $Y$.

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

A router works properly if all of the following hold:

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

The power needed to operate a 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, \dots, P_{2N+K})$.

Build a router that satisfies all of the following:

• it has exactly $N$ input nodes and exactly $N$ output nodes;
• it uses at most $M_{lim}$ direct connections;
• its maximum power is at most $P_{lim}$;
• it uses at most $500\,000$ nodes in total, that is $N_{tot} = 2N + K \le 500\,000$.

Several routers meet these requirements, so only one of them counts as correct: the lexicographically smallest one under the rule given in the output format.

The first and only line contains three integers $N$, $M_{lim}$ and $P_{lim}$, separated by spaces. $N$ is the number of input nodes and also the number of output nodes, $M_{lim}$ is the largest number of direct connections allowed, and $P_{lim}$ is the largest power the router may use.

$1 \le N \le 250$, $1 \le M_{lim} \le 1\,000\,000$, $1 \le P_{lim} \le 1\,000\,000$. The input always satisfies $N^2 \le M_{lim}$ and $N \le P_{lim}$.

On the first line print the total number of nodes $N_{tot} = 2N + K$ and the number of direct connections $M$, separated by a space. On each of the next $M$ lines print one direct connection as a pair $X$ $Y$, meaning a direct connection runs from node $X$ to node $Y$. Print the connections sorted by increasing $X$, and by increasing $Y$ when $X$ ties.

Read the whole output as the integer sequence $N_{tot}, M, X_1, Y_1, \dots, X_M, Y_M$. Among the outputs of all routers that meet the requirements, print the lexicographically smallest such sequence.