CF1948E Clique Partition

给定两个整数 $n$ 和 $k$。有一个包含 $n$ 个顶点的图，顶点编号从 $1$ 到 $n$，初始时没有边。 你需要为每个顶点分配一个整数，记为 $a_i$，表示第 $i$ 个顶点上的整数。所有 $a_i$ 应当是 $1$ 到 $n$ 之间的互不相同的整数。 分配完整数后，对于每一对顶点 $(i, j)$，如果 $|i - j| + |a_i - a_j| \le k$，就在它们之间添加一条边。 你的目标是构造一个可以被划分为最少数量团（对于给定的 $n$ 和 $k$）的图。每个顶点应恰好属于一个团。回忆一下，团是指其中任意两点都有边相连的顶点集合。 由于 BledDest 的编程能力有限，他无法解决“给定一个图，划分为最少数量团”的问题。因此你还需要输出具体的划分方案。

第一行包含一个整数 $t$（$1 \le t \le 1600$），表示测试用例的数量。 每个测试用例包含一行两个整数 $n$ 和 $k$（$2 \le n \le 40$；$1 \le k \le 2n$）。

对于每个测试用例，输出三行： - 第一行输出 $n$ 个互不相同的整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），表示分配给每个顶点的值； - 第二行输出一个整数 $q$（$1 \le q \le n$），表示将图划分为的团的数量； - 第三行输出 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le q$），表示每个顶点所属的团编号。如果两个顶点 $u$ 和 $v$ 满足 $c_u = c_v$，则它们属于同一个团。 如果有多组答案，输出任意一组均可。

由 ChatGPT 4.1 翻译