CF1991D.Prime XOR Coloring

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

给定一个无向图，该图有 $n$ 个顶点，编号从 $1$ 到 $n$ 。当且仅当 $u \oplus v$ 是一个质数时，顶点 $u$ 和顶点 $v$ 之间存在一条边，其中 $\oplus$ 表示按位异或运算。

请使用最少的颜色对图中的所有顶点进行染色，使得任意两个直接相连的顶点颜色不同。

每个测试点包含多组测试数据。第一行包含一个整数 $t$ （ $1 \le t \le 500$ ），表示测试数据的组数。

接下来每组测试数据包含一行，一个整数 $n$ （ $1 \le n \le 2 \cdot 10^5$ ），表示图中顶点的数量。

保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$ 。

对于每组测试数据，输出两行。

第一行输出一个整数 $k$ （ $1 \le k \le n$ ），表示所需的最小颜色数。

第二行输出 $n$ 个整数 $c_1, c_2, \ldots, c_n$ （ $1 \le c_i \le k$ ），表示每个顶点的颜色。

如果有多种方案，输出任意一种均可。

输入#1

输出#1

1
1
2
1 2
2
1 2 2
3
1 2 2 3
3
1 2 2 3 3
4
1 2 2 3 3 4

在第一个测试样例中，最小颜色数为 $1$ ，因为只有一个顶点。

在第二个测试样例中，最小颜色数为 $2$ ，因为 $1$ 和 $2$ 之间有一条边（ $1 \oplus 2 = 3$ ，是质数）。

在第三个测试样例中，最小颜色数仍为 $2$ ，因为 $2$ 和 $3$ 可以染成相同的颜色，因为它们之间没有边（ $2 \oplus 3 = 1$ ，不是质数）。

在第四个测试样例中，可以证明最小颜色数为 $3$ 。

在第五个测试样例中，可以证明最小颜色数为 $3$ 。

在第六个测试样例中，可以证明最小颜色数为 $4$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?