Two Out of Three

### **题目描述** 给定一个数组 $a_1, a_2, ..., a_n$。你需要找到一个数组 $b_1$, $b_2$, ..., $b_n$，其中包含数字 $1, 2, 3$，使得以下三个条件中恰好有两个条件被满足： - 存在 $1\le i, j\le n$，使得 $a_i=a_j,b_i=1,b_j=2$。 - 存在 $1\le i, j\le n$，使得 $a_i=a_j,b_i=1,b_j=3$。 - 存在 $1\le i, j\le n$，使得 $a_i=a_j,b_i=2,b_j=3$。 如果不存在这样的数组 $b$，请报告不可以。 ### **输入格式** 每个测试点多测。第一行输入一个整数 $t$，表示数据组数。对于每一组数据： 第一行输入一个整数 $n$ $(1\le n\le 100)$，表示数组 $a$ 的长度。 第二行读入 $n$ 个整数 $a_1,a_2,...,a_n$ $(1\le a_i\le 100)$，代表数组 $a$。 ### **输出格式** 对于每组数据输出一行。若无解，则输出 `-1`。否则输出一个由 $1,2,3$ 组成的数组 $b$，恰好满足两条性质。如果有多个合法数组，输出任一即可。 ### **说明/提示** 第一个数组 $a$，合法数组可以是 $b=[1,2,3,1,1,1]$。当 $i = 4,j = 2$ 时，满足性质一。当$i = 6,j = 3$ 时满足性质二。数组 $b$ 无法满足性质三，所以恰好满足两条，合法。

You are given an array $ a_1, a_2, \ldots, a_n $ . You need to find an array $ b_1, b_2, \ldots, b_n $ consisting of numbers $ 1 $ , $ 2 $ , $ 3 $ such that exactly two out of the following three conditions are satisfied: 1. There exist indices $ 1 \leq i, j \leq n $ such that $ a_i = a_j $ , $ b_i = 1 $ , $ b_j = 2 $ . 2. There exist indices $ 1 \leq i, j \leq n $ such that $ a_i = a_j $ , $ b_i = 1 $ , $ b_j = 3 $ . 3. There exist indices $ 1 \leq i, j \leq n $ such that $ a_i = a_j $ , $ b_i = 2 $ , $ b_j = 3 $ . If such an array does not exist, you should report it.

Each test contains multiple test cases. The first line contains a single integer $ t $ $ (1 \leq t \leq 500) $ — the number of test cases. Each test case is described as follows. The first line of each test case contains an integer $ n $ $ (1 \leq n \leq 100) $ — the length of the array $ a $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ $ (1 \leq a_i \leq 100) $ — the elements of the array $ a $ .

For each test case, print -1 if there is no solution. Otherwise, print $ b_1, b_2, \ldots, b_n $ — an array consisting of numbers $ 1 $ , $ 2 $ , $ 3 $ that satisfies exactly two out of three conditions. If there are multiple possible answers, you can print any of them.

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 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

In the first test case, $ b = [1, 2, 3, 1, 1, 1] $ satisfies condition $ 1 $ because for $ i = 4 $ , $ j = 2 $ : $ a_i = a_j $ , $ b_i = 1 $ , and $ b_j = 2 $ . It also satisfies condition $ 2 $ because for $ i = 6 $ , $ j = 3 $ : $ a_i = a_j $ , $ b_i = 1 $ , and $ b_j = 3 $ . However, it does not satisfy condition $ 3 $ . In total, exactly two out of three conditions are satisfied.