---
title: Kaladėlės
---

Turite į eilę surikiuotų $n$ medinių kaladėlių, kurios nudažytos $k$ skirtingų spalvų. Kaladėlių spalvos nurodytos skaičiais $c_1, c_2, \dots, c_n$, kurių visi yra nuo $1$ iki $k$.

Spalva yra laikoma _subalansuota_, jeigu tos spalvos kaladėlių vidutinė pozicija yra lygi $(n+1)/2$. Turėkite omenyje, kad šis skaičius nebūtinai bus sveikasis.

![Blocks with colors 1, 2, 2, 1, 3, 1, 2](files/blocks.svg "=440x")

Pavyzdžiui, jei $7$ kaladėlės yra išdėliotos taip, kaip parodyta aukščiau, vidutinė $1$ spalvos kaladėlių pozicija yra $(1 + 4 + 6) / 3 = 11/3$, vidutinė spalvos $2$ pozicija yra $(2 + 3 + 7) / 3 = 4$ ir vidutinė spalvos $3$ pozicija yra $5$. Kadangi $(7+1)/2=4$, spalva $2$ yra subalansuota, bet spalvos $1$ ir $3$ – ne.

Ar galite išrikiuoti kaladėles taip, kad visos spalvos būtų subalansuotos?

# Pradiniai duomenys

Pirmoje eilutėje pateiktas testų skaičius $t$.

Kitose eilutėse yra pateikti testai, kurių kiekvieną sudaro lygiai dvi eilutės:

Pirmoje eilutėje eilutėje pateikti sveikieji skaičiai $n$ ir $k$ – kaladėlių ir skirtingų spalvų skaičius.

Antroje eilutėje pateiktos kaladėlių spalvos: $c_1, c_2, \dots, c_n$. Kiekvienos spalvos bus bent viena kaladėlė.

# Išvestis

Kiekvienam testui išveskite "`YES`", jei sprendinys egzistuoja, arba "`NO`", jei neegzistuoja. Jei sprendinys egzistuoja, antroje eilutėje išveskite vieną galimų kaladėlių išrikiavimų. Išspausdinkite $n$ sveikųjų skaičių, apibūdinančių išrikiuotų kaladėlių spalvas.

# Ribojimai

- $1 \le t \le 100$
- $1 \le k \le n \le 2 \cdot 10^5$
- $1 \le c_1, c_2, \dots, c_n \le k$
- Visų $n$ suma neviršys $2 \cdot 10^5$

# Pavyzdys

Pradiniai duomenys:
```
3
7 2
1 1 1 1 2 2 2
2 2
1 2
2 1
1 1
```

Išvestis:
```
YES
1 2 2 1 1 1 2
NO
YES
1 1
```

_Paaiškinimas_: Pirmo testo atsakymo spalva $1$ yra subalansuota, nes jos vidutinė pozicija yra $(1 + 4 + 5 + 6) / 4 = 4$, kuri yra lygi $(n + 1) / 2$. Taip pat spalvos $2$ vidutinė pozicija yra $(2 + 3 + 7) / 3 = 4$, todėl abi spalvos yra subalansuotos.

Antrame teste yra du galimi kaladėlių išrikiavimo būdai, bet nė vienu atveju spalvos nebus subalansuotos.

Trečiame teste yra dvi $1$ spalvos kaladėlės, kurių pozicijos yra $1$ ir $2$. Pozicijų vidurkis yra $3/2$, todėl spalva $1$ yra subalansuota.

# Vertinimas

| Dalinė užduotis | Ribojimai | Taškai    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 3$   | [score=1] |
| 2       | $n \le 15$  | [score=2] |
| 3       | Daugiausiai vienos spalvos kaladėlių bus nelyginis skaičius | [score=3] |
| 4       | Visų spalvų kaladėlių skaičius yra vienodas | [score=4] |
| 5       | $k \le 15$  | [score=5] |
| 6       | Papildomų ribojimų nėra  | [score=6] |
