Gegeben sind ganze Zahlen $n, m > 0$ sowie ganze Zahlen $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$. Konstruiere einen Baum $T$ mit $n$ Knoten $V = \{v_1, v_2, \dots, v_n\}$, der folgende Bedingung erfüllt: Für jeden Knoten $v_i$ mit $a_i \ne -1$ muss der Rest des Grades $\deg_T(v_i)$ bei Division durch $m$ gleich $a_i$ sein. Falls $a_i = -1$ ist, gibt es keine Einschränkungen für den Grad von $v_i$.

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl $t$, die Anzahl der Testfälle ($1 \le t \le 5 \cdot 10^5$). Für jeden Testfall gilt:

Die erste Zeile enthält zwei ganze Zahlen, $n$ und $m$, die die Anzahl der Knoten im Baum und den Modul bezeichnen ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$).

Die nächste Zeile enthält $n$ ganze Zahlen $a_1, a_2, \dots, a_n$, die die geforderten Reste angeben ($-1 \le a_i < m$).

Die Summe von $n$ über alle Testfälle hinweg überschreitet nicht $5 \cdot 10^5$.

Ausgabe

Gib für jeden Testfall, falls ein solcher Baum mit $n$ Knoten existiert, „YES“ (Groß-/Kleinschreibung beliebig) aus, gefolgt von $n - 1$ Zeilen mit jeweils zwei ganzen Zahlen, die die Endpunkte jeder Kante angeben. Andernfalls gib „NO“ (Groß-/Kleinschreibung beliebig) aus.

Beispiel

Eingabe

6
1 5
0
2 3
1 1
5 4
0 1 1 1 1
6 2
1 0 0 0 0 1
3 2
1 1 1
4 10
3 3 1 1

Ausgabe

YES
YES
1 2
YES
1 2
1 3
1 4
1 5
YES
1 2
2 3
3 4
4 5
5 6
NO
NO

Hinweis

Im ersten Testfall sollen wir einen Baum mit $n = 1$ Knoten, $m = 5$ und dem Gradrest-Array $b = [0]$ konstruieren. Mit nur einem Knoten kann es keine Kanten geben, also gibt es genau einen möglichen Baum: einen einzelnen Knoten vom Grad $0$. Da $0 \bmod 5 = 0$ gilt, erfüllt er die Anforderung; daher lautet die Antwort „YES“.

Im zweiten Testfall benötigen wir einen Baum auf $n = 2$ Knoten mit $m = 3$ und den Resten $b = [1, 1]$, was bedeutet, dass beide Grade kongruent zu $1$ modulo $3$ sein müssen. Auf zwei Knoten gibt es nur einen Baum: die einzelne Kante $1-2$. Seine Grade sind $(1, 1)$, und tatsächlich gilt $1 \bmod 3 = 1$, also lautet die Antwort „YES“, und die Ausgabe „1 2“ ist gültig.

Im dritten Testfall benötigen wir $n = 5$, $m = 4$ mit den Resten $b = [0, 1, 1, 1, 1]$: Der erste Knoten muss einen durch $4$ teilbaren Grad haben, während die anderen vier Knoten $\text{degree} \equiv 1 \pmod 4$ erfüllen müssen. Eine natürliche Konstruktion ist ein Stern mit Zentrum im Knoten $1$: Verbinde $1$ mit jedem anderen Knoten. Dann gilt $\deg(1) = 4$ und $4 \bmod 4 = 0$, während jeder der Knoten $2, 3, 4, 5$ den Grad $1$ hat und $1 \bmod 4 = 1$ gilt. Daher lautet die Antwort „YES“, und die Kanten „1 2“, „1 3“, „1 4“, „1 5“ funktionieren.

Im vierten Testfall benötigen wir einen Baum mit $n = 6$, $m = 2$ und den Resten $b = [1, 0, 0, 0, 0, 1]$, d. h. die Endpunkte müssen ungeraden Grad und die vier mittleren Knoten geraden Grad haben. Modulo $2$ ist dies eine reine Paritätsbedingung. Der einfache Pfad $1-2-3-4-5-6$ passt perfekt: Die Knoten $1$ und $6$ haben Grad $1$ (ungerade), und die Knoten $2, 3, 4, 5$ haben Grad $2$ (gerade). Folglich lautet die Antwort „YES“, und die Pfadkanten sind korrekt.

Im fünften Testfall sollen wir einen Graphen (und damit insbesondere einen Baum) auf $n = 3$ mit $m = 2$ und $b = [1, 1, 1]$ konstruieren, sodass jeder Knoten ungeraden Grad haben muss. Dies ist unmöglich: In jedem ungerichteten Graphen ist die Anzahl der Knoten mit ungeradem Grad stets gerade, sodass drei ungerade Grade für keine Kantenmenge auftreten können. Daher lautet das Urteil „NO“.

Im sechsten Testfall haben wir $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$. Da $m > n - 1 = 3$ ist, stimmt der Rest modulo $10$ mit dem Grad selbst überein, sodass wir genau $\deg = [3, 3, 1, 1]$ fordern. Das erzwingt, dass zwei Knoten zu allen anderen benachbart sind (Grad $3$ in einem Graphen mit $4$ Knoten), und für $n > 2$ bildet jedes solche Paar zusammen mit einem beliebigen dritten Knoten zwangsläufig einen Kreis. Ein Baum kann keine Kreise enthalten, also lautet das Urteil ebenfalls „NO“.