408339: GYM103102 C 3-colorings
Description
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?
InputThere is no input for this problem.
OutputFirst, 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$$$.
ExampleInput-Output
3 2 1 2 2 3 1 1 3 0Note
The sample output is given as an example. It contains the output for $$$k = 1, 2$$$.