CF1328D Carousel

旋转木马由 $n$ 个动物模型组成。模型按照旋转木马的移动顺序从 $1$ 到 $n$ 编号。因此，在第 $n$ 个模型之后，编号为 $1$ 的模型接着出现。每个模型都有自己的类型——即该模型所对应的动物类型（如马、虎等）。第 $i$ 个模型的动物类型为 $t_i$。  例如，当 $n=9$ 且 $t=[5, 5, 1, 15, 1, 5, 5, 1, 1]$ 时，旋转木马如上图所示。你希望用若干种颜色为每个模型上色。你认为，如果旋转木马上有两个相邻的不同类型的模型被涂成了相同的颜色，这样会很无聊。 你的任务是为所有模型上色，使得所用颜色的种类数尽可能少，并且不存在两个相邻的不同类型的模型被涂成相同颜色的情况。如果你使用了恰好 $k$ 种不同的颜色，则模型的颜色编号应为 $1$ 到 $k$ 的整数。

输入包含一个或多个测试用例。 第一行包含一个整数 $q$（$1 \le q \le 10^4$），表示测试用例的数量。接下来是 $q$ 个测试用例。 每个测试用例包含两行。 第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$），表示旋转木马上的模型数量。模型按照旋转木马的移动顺序从 $1$ 到 $n$ 编号。假设第 $n$ 个模型后面是第 $1$ 个模型。 第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$（$1 \le t_i \le 2 \cdot 10^5$），其中 $t_i$ 表示第 $i$ 个模型的动物类型。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出 $q$ 组答案，每组答案输出两行。 第一行输出一个整数 $k$，表示所用的最小颜色种类数。 第二行输出 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le k$），其中 $c_i$ 表示第 $i$ 个模型的颜色编号。如果有多种方案，输出任意一种均可。

由 ChatGPT 4.1 翻译