3-colorings#10882
This problem has no input. Note that you must submit a program that prints the answer, not a text file.
A valid -coloring of a graph is an assignment of a color (number) from the set {1, 2, 3} to each of the vertices such that the endpoints of every edge have different colors. The number of such colorings for a graph with vertices does not exceed 3^n.
You work at a company and aim to become a specialist in constructing graphs with a prescribed number of -colorings. One day you learn that in the evening you will receive an order for a graph that has exactly valid -colorings. The exact value of is unknown to you; you only know that 1 \le k \le 500.
You do not want to wait until the value of becomes known, so you construct in advance a graph containing at most vertices. After the value of is given, you may add at most edges to the graph so that the resulting graph has exactly valid -colorings.
Can you do it?
There is no input.
First, print and m~(1 \le n \le 19, 0 \le m \le n \cdot (n - 1) / 2) — the number of vertices and edges of the initial graph (constructed in advance). Then print lines of the form — the edges of the graph.
Next, for each from to , perform the following actions.
Print — the number of edges you add for this particular value of k~(0 \le e \le 17). Then print lines of the form — the edges to be added.
The graph must not contain self-loops, and for each all m + e edges used must be pairwise distinct. The number of valid -colorings of the graph for the given must be exactly .
The example shows an output for k = 1, 2.
Example 1