Hide

Problem H
Chair Game

Submissions to this problem will only be marked as accepted if they receive at least a score of 100
Languages en is

Consider a game with $n$ players and $n$ chairs. The chairs will be arranged in a circle, and each player will sit on a chair. There is also a bell which will ring some number of times during the game. Each chair has an integer between $1$ and $n$: the number of steps the player who sits on that chair must move clockwise when the bell rings. A chair arrangement is valid if each chair will have exactly one player after the bell rings. Your task is to find a valid chair arrangement or state that there is no such arrangement.

Input

The first line has an integer $t$: the number of tests. There are at most $1\, 000$ tests. After this, each test consists of two lines. The first line has an integer $n$, the number of chairs. There are at most $100$ chairs. The second line has integers $s_1,s_2,\dots ,s_ n$: the numbers on the chairs. For all $i$ we have $1 \leq s_ i \leq n$.

Output

For each test, first print YES if there is a valid chair arrangement and NO otherwise. If the answer is YES, also print a possible arrangement clockwise. If there are several valid arrangements, you can print any of them.

Scoring

Group

Points

Constraints

1

8

$1 \leq n \leq 8$.

2

5

$s_ i \neq s_ j$ ef $i \neq j$, that is to say all the $s_ i$ are different within each case.

3

4

$1 \leq s_ i \leq 2$.

4

7

$1 \leq s_ i \leq 3$.

5

12

$1 \leq s_ i \leq 4$.

6

15

$1 \leq s_ i \leq 5$.

7

20

$1 \leq n \leq 16$.

8

29

No further constraints.

Sample Input 1 Sample Output 1
3
4
1 1 1 1
4
1 1 1 2
5
4 1 2 1 2
YES
1 1 1 1 
NO
YES
2 4 1 1 2 

Please log in to submit a solution to this problem

Log in