chairgame (NOINordic contest)
Time limit: 1 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: network flow, bipartite matching, optimization

# NOI 2024 Chair Game

[TASK](https://cses.fi/495/task/B/) [SUBMIT](https://cses.fi/495/submit/B/) [RESULTS](https://cses.fi/495/view/B/)

**Time limit:** 1.00 s **Memory limit:** 512 MB

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.

After this, each test consists of two lines. The first line has an integer $n$. The second line has integers $s_1, s_2, \dots, s_n$: the numbers on the chairs.

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

## Constraints

*   $1 \le t \le 1000$
*   $1 \le n \le 100$
*   $1 \le s_i \le n$ for $i = 1, 2, \dots, n$

## Example

Input:

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

Output:

```
YES
1 1 1 1
NO
YES
2 4 1 1 2
```

## Tasks

*   **A** [Anime Shops](https://cses.fi/495/task/A)
*   **B** Chair Game
*   **C** [Thin Ice](https://cses.fi/495/task/C)

## Your submissions

## Subtask 1 (8 points)

*   $1 \le n \le 8$

## Subtask 2 (5 points)

*   $s_i \ne s_j$ if $i \ne j$ (i.e. each value is distinct)

## Subtask 3 (4 points)

*   $1 \le s_i \le 2$ for $i = 1, 2, \dots, n$

## Subtask 4 (7 points)

*   $1 \le s_i \le 3$ for $i = 1, 2, \dots, n$

## Subtask 5 (12 points)

*   $1 \le s_i \le 4$ for $i = 1, 2, \dots, n$

## Subtask 6 (15 points)

*   $1 \le s_i \le 5$ for $i = 1, 2, \dots, n$

## Subtask 7 (20 points)

*   $1 \le n \le 16$

## Subtask 8 (29 points)

*   No restrictions.

Starter code:

Grader code:

Setup script:

Evaluation script: