Router 1

Henry and Hetty were hired by a networking company. Their first project is a new router, the Connect Ethernet Operating Interface, 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, each joining two 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$ can send data to $Y$ and $X \ne Y$, the data path from $X$ to $Y$ is the set of direct connections $\{(A_1, A_2), (A_2, A_3), \ldots, (A_{L-1}, A_L)\}$ with $L \ge 2$, $A_1 = X$ and $A_L = Y$.

A router works properly when all of the following 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 any two nodes $X$ and $Y$ with $X \ne Y$, if $X$ can send data to $Y$, then $Y$ cannot send data to $X$;
• for any two nodes $X$ and $Y$ with $X \ne Y$, if $X$ can send data to $Y$, then the data path from $X$ to $Y$ is unique. In particular, any 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$. Writing $N_{tot} = 2N + K$ for the total number of nodes, the maximum power used by the router is $P_{max} = \max(P_1, P_2, \ldots, P_{N_{tot}})$.

You are given $N$, $M_{lim}$ and $P_{lim}$. Build a router that works properly, has exactly $N$ input nodes and $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. Several routers meet such a specification, so the output section fixes the single one you must print.

One line with three integers $N$, $M_{lim}$ and $P_{lim}$: the number of input nodes and of output nodes, the largest number of direct connections allowed, and the largest power the router may use ($1 \le N \le 1000$, $1 \le M_{lim} \le 10^6$, $1 \le P_{lim} \le 10^6$).

It is guaranteed that $N \le P_{lim}$ and that the router described in the output section uses at most $M_{lim}$ direct connections.

Print the router picked by the rule below.

If $N \times N \le P_{lim}$, print the router with one internal node. It has $N_{tot} = 2N + 1$ nodes and $M = 2N$ direct connections: first the connections $i \to 2N+1$ for $i = 1, 2, \ldots, N$ in increasing order of $i$, then the connections $2N+1 \to N+j$ for $j = 1, 2, \ldots, N$ in increasing order of $j$.

Otherwise print the router with no internal node. It has $N_{tot} = 2N$ nodes and $M = N \times N$ direct connections, namely $i \to N+j$ for every pair $(i, j)$, sorted by $i$ increasing and, for equal $i$, by $j$ increasing.

The first line holds $N_{tot}$ and $M$ separated by a space. Each of the next $M$ lines holds two integers $X$ and $Y$, meaning a direct connection from node $X$ to node $Y$ was built.