---
title: Blöcke
---

Du hast $n$ Holzblöcke in $k$ verschiedenen Farben, die in einer Reihe angeordnet sind. Die Farben der Blöcke sind $c_1, c_2, \dots, c_n$, alle zwischen $1$ und $k$.

Eine Farbe gilt als _ausgewogen_, wenn die durchschnittliche Position der Blöcke dieser Farbe $(n+1)/2$ beträgt. Beachte, dass diese Zahl nicht unbedingt eine ganze Zahl ist.

![Blöcke mit den Farben 1, 2, 2, 1, 3, 1, 2](files/blocks.svg "=440x")

Wenn beispielsweise $7$ Blöcke wie oben angeordnet sind, beträgt die durchschnittliche Position der Farbe $1$: $(1 + 4 + 6) / 3 = 11/3$, die durchschnittliche Position der Farbe $2$: $(2 + 3 + 7) / 3 = 4$ und die durchschnittliche Position der Farbe $3$: $5$. Da $(7+1)/2=4$ ist, ist die Farbe $2$ ausgewogen, die Farben $1$ und $3$ jedoch nicht.

Kannst du die Blöcke so anordnen, dass alle Farben ausgewogen sind?

# Eingabe

Die erste Zeile enthält eine einzelne ganze Zahl $t$: die Anzahl der Testfälle.

Die folgenden Zeilen beschreiben die Testfälle, die jeweils aus zwei Zeilen wie folgt bestehen:

Die erste Zeile enthält zwei ganze Zahlen $n$ und $k$: die Anzahl der Blöcke und die Anzahl der verschiedenen Farben.

Die zweite Zeile enthält die Farben der Blöcke $c_1, c_2, \dots, c_n$. Es gibt mindestens einen Block jeder Farbe.

# Ausgabe

Gib für jeden Testfall „`YES`“ aus, wenn eine Lösung existiert, und andernfalls „`NO`“. Wenn eine Lösung existiert, beschreibe eine mögliche Reihenfolge, indem du $n$ ganze Zahlen in einer weiteren Zeile ausgibst: Die Farbe des Blocks an jeder Position.

# Beschränkungen

- $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$
- Die Summe aller $n$ beträgt höchstens $2 \cdot 10^5$

# Beispiel

Eingabe:
```
3
7 2
1 1 1 1 2 2 2
2 2
1 2
2 1
1 1
```

Ausgabe:
```
YES
1 2 2 1 1 1 2
NO
YES
1 1
```

_Erklärung_: In der Ausgabe des ersten Testfalls ist die Farbe $1$ ausgewogen, da ihre durchschnittliche Position $(1 + 4 + 5 + 6) / 4 = 4$ beträgt, was $(n + 1) / 2$ entspricht. Analog dazu beträgt die durchschnittliche Position der Farbe $2$ $(2 + 3 + 7) / 3 = 4$. Beide Farben sind daher ausgewogen.

Im zweiten Testfall führt keine der beiden möglichen Reihenfolgen zu einem Gleichgewicht der Farben.

In der Ausgabe des dritten Testfalls erscheinen Blöcke der Farbe $1$ an den Positionen $1$ und $2$. Der Durchschnitt beträgt $3/2$, daher ist die Farbe $1$ ausgewogen.

# Bewertung

| Teilaufgabe | Beschränkungen | Punkte |
| :-----: | ----------- | :-------: |
| 1       | $n \le 3$   | [score=1] |
| 2       | $n \le 15$  | [score=2] |
| 3       | Es gibt höchstens eine Farbe, die eine ungerade Anzahl von Malen vorkommt | [score=3] |
| 4       | Alle Farben kommen gleich oft vor | [score=4] |
| 5       | $k \le 15$  | [score=5] |
| 6       | Keine zusätzlichen Beschränkungen | [score=6] |
