eolymp
Competitions

2020 SEERC

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 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 1k500.

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?

Input

There is no input for this problem.

Output

First, output n and m (1n19, 1mn * (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 (1e17). 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.

Example

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

Time limit 1 second
Memory limit 128 MiB
Input example #1
Output example #1
3 2
1 2
2 3
1
1 3
0
Source 2020 SEERC South Eastern European Regional Programming Contest, Vinnica & Bucharest, May 23, Problem C