P10738 [SEERC 2020] 3-colorings

**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$.

None.

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)$.

The sample only provides examples for $k=1$ and $k=2$. Translated by ChatGPT 5