Problem Description

This is an output-only problem.

A valid “3-coloring” of a graph is defined as follows:

• The color of each vertex can only be in $\{1,2,3\}$.

• For every pair of adjacent vertices $(u,v)$, the color of $u$ must be different from the color of $v$.

It can be proven that the maximum number of “3-colorings” of a graph is $3^n$.

Now you need to construct a graph. Initially, it has $n \ (1 \leq n \leq 19)$ vertices and $m \ (1 \leq m \leq \frac{n(n-1)}{2})$ undirected edges. Then, for each $k$ with $1 \leq k \leq 500$, you may add at most $17$ undirected edges so that the number of “3-colorings” of the graph becomes $6k$.

Input Format

None.

Output Format

The first line contains $n,m$, representing the number of vertices and edges in the graph you construct.

Then output $m$ lines, each with two integers $u,v$, indicating that there is an undirected edge $(u,v)$.

Then for $k$ from $1$ to $500$, for each $k$ output the number of edges you want to add, followed by that many lines of added edges $(u,v)$.

3 2
1 2
2 3
1
1 3
0

Hint

The sample only provides examples for $k=1$ and $k=2$.

Translated by ChatGPT 5