# 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 **1** ≤ **k** ≤ **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 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** (**1** ≤ **n** ≤ **19**, **1** ≤ **m** ≤ **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** ≤ **e** ≤ **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**.

#### Example

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

3 2 1 2 2 3 1 1 3 0