3-colorings#12837

3-colorings

2 seconds
256 megabytes
Very hard

This is an output-only problem. Note that you still have to send code which prints the output, not a text file.

A valid -coloring of a graph is an assignment of colors (numbers) from the set \{1, 2, 3\} to each of the vertices such that for any edge of the graph, vertices and have a different color. There are at most 3^n such colorings for a graph with vertices.

You work in a company, aiming to become a specialist in creating graphs with a given number of -colorings. One day, you get to know that in the evening you will receive an order to produce a graph with exactly -colorings. You don't know the exact value of , only that 1 \le k \le 500.

You don't want to wait for the specific value of to start creating the graph. Therefore, you build a graph with at most vertices beforehand. Then, after learning that particular , you are allowed to add at most edges to the graph, to obtain the required graph with exactly -colorings.

Can you do it?

Input

There is no input for this problem.

Output

First, output and (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 lines of form  — the edges of the graph.

Next, for every from to do the following:

Output — the number of edges you will add for this particular (1 \le e \le 17). Then, output lines of the form  — the edges you will add to your graph.

There can't be self-loops, and for every , all m + e edges you use have to be pairwise distinct. The number of -colorings of the graph for a particular has to be exactly .

Examples

Example 1

Loading
Loading

Note

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