← 返回题目列表

Codeforces · 1894/B

B. 三分之二

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

给你一个数组 $$$a_1, a_2, \ldots, a_n$$$。您需要找到一个由数字 $$$1$$$、$$$2$$$、$$$3$$$ 组成的数组 $$$b_1, b_2, \ldots, b_n$$$,并且满足以下三个条件中的两个:

1. 存在索引 $$$1 \leq i, j \leq n$$$ 使得 $$$a_i = a_j$$$, $$$b_i = 1$$$, $$$b_j = 2$$$。
2. 存在索引 $$$1 \leq i, j \leq n$$$ 使得 $$$a_i = a_j$$$, $$$b_i = 1$$$, $$$b_j = 3$$$。
3. 存在索引 $$$1 \leq i, j \leq n$$$ 使得 $$$a_i = a_j$$$, $$$b_i = 2$$$, $$$b_j = 3$$$。

如果这样的数组不存在,您应该报告它。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 500)$$$ — 测试用例的数量。每个测试用例描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 100)$$$ - 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 100)$$$ - 数组 $$$a$$$ 的元素。

输出

对于每个测试用例,如果没有解决方案,则打印 -1。否则,打印 $$$b_1, b_2, \ldots, b_n$$$ - 由数字 $$$1$$$、$$$2$$$、$$$3$$$ 组成的数组,恰好满足三个条件中的两个。如果有多个可能的答案,您可以打印其中任何一个。

示例

输入 #1

9
6
1 2 3 2 2 3
7
7 7 7 7 7 7 7
4
1 1 2 2
7
1 2 3 4 5 6 7
5
2 3 3 3 2
3
1 2 1
9
1 1 1 7 7 7 9 9 9
1
1
18
93 84 50 21 88 52 16 50 63 1 30 85 29 67 63 58 37 69

输出 #1

1 2 3 1 1 1 
-1
3 2 2 1 
-1
2 1 2 1 3 
-1
1 1 2 2 1 2 2 3 3
-1
3 2 1 3 3 3 3 2 2 1 1 2 3 1 3 1 1 2

注意

在第一个测试用例中,$$$b = [1, 2, 3, 1, 1, 1]$$$ 满足条件 $$$1$$$,因为对于 $$$i = 4$$$,$$$j = 2$$$:$$$a_i = a_j$$$、$$$b_i = 1$$$ 和 $$$b_j = 2$$$。它还满足条件 $$$2$$$,因为对于 $$$i = 6$$$、$$$j = 3$$$:$$$a_i = a_j$$$、$$$b_i = 1$$$ 和 $$$b_j = 3$$$。然而,它不满足条件$$$3$$$。总共,正好满足三个条件中的两个。