Problems
3-colorings
3-colorings
\textbf{This is an output-only problem}. Note that you still have to send code which prints the output, not a text file.
A valid 3-coloring of a graph is an assignment of colors (numbers) from the set $\{1, 2, 3\}$ to each of the $n$ vertices such that for any edge $(a, b)$ of the graph, vertices $a$ and $b$ have a different color. There are at most $3n$ such colorings for a graph with $n$ vertices.
You work in a company, aiming to become a specialist in creating graphs with a given number of 3-colorings. One day, you get to know that in the evening you will receive an order to produce a graph with exactly $6k$ 3-colorings. You don't know the exact value of $k$, only that $1 \le k \le 500$.
You don't want to wait for the specific value of $k$ to start creating the graph. Therefore, you build a graph with at most $19$ vertices beforehand. Then, after learning that particular $k$, you are allowed to add at most $17$ edges to obtain the required graph with exactly $6k$ 3-colorings.
Can you do it?
\InputFile
There is no input for this problem.
\OutputFile
First, output $n$ and $m~(1 \le n \le 19, 1 \le m \le n \cdot (n - 1) / 2)$ --- the number of vertices and edges of the initial graph (the one built beforehand). Then, output $m$ lines of form $(u, v)$ --- the edges of the graph.
Next, for every $k$ from $1$ to $500$ do the following:
Output $e$ --- the number of edges you will add for this particular $k~(1 \le e \le 17)$. Then, output $e$ lines of the form $(u, v)$ --- the edges you will add to your graph.
There can't be self-loops, and for every $k$, all $m + e$ edges you use have to be pairwise distinct. The number of 3-colorings of the graph for a particular $k$ has to be exactly $6k$.
\Examples
The sample output is given as an example. It contains the output for $k = 1, 2$.
Input example #1
Output example #1
3 2 1 2 2 3 1 1 3 0