Two Out of Three
Contest: Codeforces Round 908 (Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
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

Example output:
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

Editorial:
By symmetry, it doesn't matter which two conditions are satisfied. Let's assume it's the conditions $$$(1, 2)$$$ and $$$(1, 3)$$$. Then the elements with $$$b_i = 2$$$ and the elements with $$$b_i = 3$$$ should not intersect. Therefore, it is sufficient to assign $$$b_i = 2$$$ and $$$b_i = 3$$$ to only one element that is common with the elements of the form $$$b_i = 1$$$ in order to satisfy the conditions $$$(1, 2)$$$ and $$$(1, 3)$$$. And these elements must be distinct in order to not satisfy the condition $$$(2, 3)$$$. Thus, we obtain the necessary condition for the existence of an answer: the array must have at least two elements that occur more than once. It is easy to see that this condition is also sufficient by constructing an example: let $$$x, y$$$ be two numbers that occur more than once in the array. Then we can assign $$$a_i = x \to b_i = 2$$$ to one of the occurrences, $$$a_i = y \to b_i = 3$$$ to one of the occurrence, and assign $$$b_i = 1$$$ to all other numbers, and this will be a suitable answer.