P10738 [SEERC 2020] 3-colorings

**这是一道仅有输出的题。** 定义一个图的有效“三色”染色为： - 每个点的颜色只能属于 $\{1,2,3\}$。 - 对于每个有边相连的顶点 $(u,v)$，$u$ 的颜色需要与 $v$ 不同。 可以证明，一个图最多的“三色”染色总数为 $3^n$ 种。 现在你需构造一个图，一开始它存在 $n \ (1 \leq n \leq 19)$ 个顶点 $m \ (1 \leq m \leq \frac{n(n-1)}{2})$ 条无向边，然后对于每个 $1 \leq k \leq 500$ 的 $k$，你可以添加至多 $17$ 条无向边使得此图的“三色”染色总数为 $6k$ 种。

无。

第一行 $n,m$，表示你构造图的点数和边数。 然后 $m$ 行，一行两个整数 $u,v$，表示 $(u,v)$ 存在一条无向边。 然后 $k$ 从 $1$ 到 $500$，每个 $k$ 输出你要添加的边数，然后再是对应行添加的边 $(u,v)$。

样例仅给出 $k=1$ 和 $k=2$ 的示例。