29781번 - Rainbow Sort 서브태스크다국어

문제

Your friend Charles gives you a challenge. He puts $\mathbf{N}$ cards on a table and arranges them in a line in an order that he chooses. Each card has a single color, and each color can be on one or more cards.

Charles then asks you to write a positive integer on each card without altering his chosen order such that:

1. The integers you write appear in non-decreasing order when cards are read from left to right.
2. Cards of the same color have the same integer written on them.
3. Cards of different colors have different integers written on them.

Finally, Charles wants you to order the colors in increasing order of written integer. For example, if blue cards have a 2ドル,ドル red cards have a 5ドル,ドル and green cards have a 3ドル,ドル the color order would be blue, green, red.

입력

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.

Each test case begins with a line containing the integer $\mathbf{N}$. The next line contains $\mathbf{N}$ integers, $\mathbf{S_1},ドル $\mathbf{S_2},ドル $\dots,ドル $\mathbf{S_N},ドル where $\mathbf{S_i}$ represents the color of the $i$-th card from the left.

출력

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the set of colors, once each, listed in the requested order. If it is impossible to write integers in the given cards while adhering to all the rules, $y$ must be IMPOSSIBLE instead.

제한

• 1ドル \le \mathbf{T} \le 100$.
• 1ドル \le \mathbf{S_i} \le 10^5,ドル for all $i$.

Test Set 1 (4점)

• 1ドル \le \mathbf{N} \le 10$.

Test Set 2 (10점)

• 1ドル \le \mathbf{N} \le 10^5$.

힌트

In Sample Case #1, there are 3ドル$ different colors on 4ドル$ cards. One possible solution is to write the following integers, in order: 1ドル,ドル 2ドル,ドル 2ドル,ドル and 3ドル$. Notice that the same integer (2ドル$) is written on both cards of color 8ドル$. Then, the order of the colors is 3ドル,ドル 8ドル,ドル 2ドル$.

In Sample Case #2, let $c_8$ and $c_2$ be the integers written in cards of color 8ドル$ and 2ドル,ドル respectively. If $c_2 \gt c_8$ then the rightmost two cards would not have their integers in non-decreasing order. If $c_2 \lt c_8$ that would happen to the second and third card from the left. Finally, $c_8 = c_2$ is forbidden by one of the rules. Therefore, there is no valid way of writing the integers in this case.