圆形旋转木马由 $$$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