408339: GYM103102 C 3-colorings

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 $$$3^n$$$ 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 the graph, to obtain the required graph with exactly $$$6k$$$ $$$3$$$-colorings.

Can you do it?

There is no input for this problem.

First, output $$$n$$$ and $$$m$$$ ($$$1 \le n \le 19$$$, $$$1 \le m \le \frac{n(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$$$.

-

3 2
1 2
2 3
1
1 3
0

The sample output is given as an example. It contains the output for $$$k = 1, 2$$$.