题目描述

这是一道仅有输出的题。

定义一个图的有效“三色”染色为：

• 每个点的颜色只能属于 $\{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)$。

3 2
1 2
2 3
1
1 3
0

提示

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