← 返回题目列表

Codeforces · 1328/D

D. 旋转木马

中文机器翻译题面 查看原题

圆形旋转木马由 $$$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\cdot10^5$$$。

输出

打印 $$$q$$$ 答案,为每个测试用例打印两行。

在第一行打印一个整数 $$$k$$$ — 图形不同颜色的最小可能数量。

在第二行中打印 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le k$$$),其中 $$$c_i$$$ 是第 $$$i$$$ 个数字的颜色。如果有多个答案,您可以打印任何一个。

示例

输入 #1

4
5
1 2 1 2 2
6
1 2 2 1 2 2
5
1 2 1 2 3
3
10 10 10

输出 #1

2
1 2 1 2 2
2
2 1 2 1 2 1
3
2 3 2 3 1
1
1 1 1