CF1328D.Carousel

The round carousel consists of $n$ figures of animals. Figures are numbered from $1$ to $n$ in order of the carousel moving. Thus, after the $n$-th figure the figure with the number $1$ follows. Each figure has its own type — the type of the animal corresponding to this figure (the horse, the tiger and so on). The type of animal of the $i$-th figure equals $t_i$.

The example of the carousel for $n=9$ and $t=[5, 5, 1, 15, 1, 5, 5, 1, 1]$.

You want to color each figure in one of the colors. You think that it's boring if the carousel contains two different figures (with the distinct types of animals) going one right after another and colored in the same color.

Your task is to color the figures in such a way that the number of distinct colors used is the minimum possible and there are no figures of the different types going one right after another and colored in the same color. If you use exactly $k$ distinct colors, then the colors of figures should be denoted with integers from $1$ to $k$.

旋转木马由 $n$ 个动物造型组成。这些造型按旋转木马的运动方向编号为 $1$ 到 $n$。因此，在第 $n$ 个造型之后，紧接着的是编号为 $1$ 的造型。每个造型都有其对应的动物种类（例如马、老虎等）。第 $i$ 个造型的动物种类为 $t_i$。

一个 $n=9$ 且 $t=[5, 5, 1, 15, 1, 5, 5, 1, 1]$ 的旋转木马示例。

你需要为每个造型染上一种颜色。你认为，如果旋转木马中存在两个种类不同的造型（即对应动物种类不同）相邻（即一个紧接在另一个之后），且它们被染成同一种颜色，那么这将显得很无趣。

你的任务是为所有造型染色，使得所用颜色种类数尽可能少，并且不存在两个种类不同且相邻的造型被染成同一种颜色。若恰好使用了 $k$ 种不同的颜色，则这些颜色需用整数 $1$ 至 $k$ 表示。

The input contains one or more test cases.

The first line contains one integer $q$ ($1 \le q \le 10^4$) — the number of test cases in the test. Then $q$ test cases follow. One test case is given on two lines.

The first line of the test case contains one integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of figures in the carousel. Figures are numbered from $1$ to $n$ in order of carousel moving. Assume that after the $n$-th figure the figure $1$ goes.

The second line of the test case contains $n$ integers $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 2 \cdot 10^5$), where $t_i$ is the type of the animal of the $i$-th figure.

The sum of $n$ over all test cases does not exceed $2\cdot10^5$.

输入包含一个或多个测试用例。

第一行包含一个整数 $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\cdot10^5$。

Print $q$ answers, for each test case print two lines.

In the first line print one integer $k$ — the minimum possible number of distinct colors of figures.

In the second line print $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le k$), where $c_i$ is the color of the $i$-th figure. If there are several answers, you can print any.

输出 $q$ 个答案，对每个测试用例输出两行。

第一行输出一个整数 $k$ —— 图形所需的不同颜色的最小可能数量。

第二行输出 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le k$），其中 $c_i$ 表示第 $i$ 个图形的颜色。若有多种答案，输出任意一种即可。