DMOPC '21 Contest 9 P5 - Chika Circle

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Chika is playing a game!

Chika got her friends arranged in a circle and gave them each a card labelled with a distinct number from to .

The game is to figure out who has which card. However, if you ask someone what card they have, they will instead reply with the minimum label of their neighbours' cards (for some reason). You have asked everyone for their answers and have recorded them in your array .

Chika already knows the answers—because she cheated. You, however, must figure out the answer. It occurs to you that the answer is not always unique; that is, even if you ask everyone, there may be multiple valid configurations that are consistent with the answers.

As such, you decide to only declare a card's value when you are convinced of it, formally, when across all configurations consistent with the answers given, the person always has the same card.

In order to have the most fun, Chika has decreed that you will play games and must answer for each.

Constraints

It is guaranteed that there is a valid arrangement of the integers from to that produce the array .

The sum of across all test cases will not exceed .

The sum of across all test cases will not exceed .

The sum of across all test cases will not exceed .

Input Specification

The first line contains the integer .

The next lines contain games. For each game, the first line contains the integer , and the next line contains integers , the responses from Chika's friends.

Output Specification

For each game, output an array of length , where the th element is either the number on the card of the th person or if the number varies across valid configurations.

Sample Input

2
5
1 3 1 4 2
4
1 3 1 3

Sample Output

3 1 0 2 0
0 0 0 0

Explanation

It can be proven that the only two valid configurations for the first game are 3 1 4 2 5 and 3 1 5 2 4.