Sono dati gli interi $n, m > 0$, così come gli interi $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$. Costruisci un albero $T$ con $n$ vertici $V = \{v_1, v_2, \dots, v_n\}$ che soddisfi la seguente condizione: per ogni vertice $v_i$ tale che $a_i \ne -1$, il resto della divisione del grado $\deg_T(v_i)$ per $m$ deve essere uguale ad $a_i$. Se $a_i = -1$, allora non ci sono restrizioni sul grado di $v_i$.
Input
La prima riga dell'input contiene un intero $t$, il numero di casi di test ($1 \le t \le 5 \cdot 10^5$). Per ciascun caso di test:
La prima riga contiene due interi, $n$ e $m$, che indicano il numero di vertici nell'albero e il modulo ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$).
La riga successiva contiene $n$ interi $a_1, a_2, \dots, a_n$ che indicano i resti richiesti ($-1 \le a_i < m$).
La somma di $n$ su tutti i casi di test non supera $5 \cdot 10^5$.
Output
Per ciascun caso di test, se esiste un tale albero con $n$ vertici, stampa "YES" (in qualsiasi combinazione di maiuscole e minuscole), seguito da $n - 1$ righe con due interi ciascuna che indicano gli estremi di ogni arco. Altrimenti, stampa "NO" (in qualsiasi combinazione di maiuscole e minuscole).
Esempio
Input
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
Output
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
Nota
Nel primo caso di test, ci viene chiesto di costruire un albero con $n = 1$ vertice, $m = 5$ e array dei resti dei gradi $b = [0]$. Con un solo vertice non possono esserci archi, quindi c'è esattamente un albero possibile: un singolo vertice di grado $0$. Poiché $0 \bmod 5 = 0$, soddisfa il requisito; quindi la risposta è "YES".
Nel secondo caso di test, abbiamo bisogno di un albero su $n = 2$ vertici con $m = 3$ e resti $b = [1, 1]$, il che significa che entrambi i gradi devono essere congrui a $1$ modulo $3$. Su due vertici c'è un solo albero: il singolo arco $1-2$. I suoi gradi sono $(1, 1)$ e in effetti $1 \bmod 3 = 1$, quindi la risposta è "YES" e stampare "1 2" è valido.
Nel terzo caso di test, abbiamo bisogno di $n = 5$, $m = 4$, con resti $b = [0, 1, 1, 1, 1]$: il primo vertice deve avere grado divisibile per $4$, mentre gli altri quattro vertici devono avere $\text{degree} \equiv 1 \pmod 4$. Una costruzione naturale è una stella centrata nel vertice $1$: collegare $1$ a ogni altro vertice. Allora $\deg(1) = 4$ e $4 \bmod 4 = 0$, mentre ciascuno di $2, 3, 4, 5$ ha grado $1$ e $1 \bmod 4 = 1$. Pertanto, la risposta è "YES" e gli archi "1 2", "1 3", "1 4", "1 5" funzionano.
Nel quarto caso di test, abbiamo bisogno di un albero con $n = 6$, $m = 2$, resti $b = [1, 0, 0, 0, 0, 1]$, cioè gli estremi devono avere grado dispari e i quattro vertici centrali devono avere grado pari. Modulo $2$, questo è puramente un vincolo di parità. Il cammino semplice $1-2-3-4-5-6$ si adatta perfettamente: i vertici $1$ e $6$ hanno grado $1$ (dispari) e i vertici $2, 3, 4, 5$ hanno grado $2$ (pari). Quindi la risposta è "YES" e gli archi del cammino sono corretti.
Nel quinto caso di test, ci viene chiesto di costruire un grafo (e quindi, in particolare, un albero) su $n = 3$ con $m = 2$ e $b = [1, 1, 1]$, quindi ogni vertice deve avere grado dispari. Ciò è impossibile: in ogni grafo non orientato, il numero di vertici di grado dispari è sempre pari, quindi avere tre gradi dispari non può accadere per alcun insieme di archi. Pertanto, il verdetto è "NO".
Nel sesto caso di test, abbiamo $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$. Poiché $m > n - 1 = 3$, il resto modulo $10$ è uguale al grado stesso, quindi richiediamo esattamente $\deg = [3, 3, 1, 1]$. Ciò costringe due vertici a essere adiacenti a tutti gli altri (grado $3$ in un grafo di $4$ vertici), e quando $n > 2$, qualsiasi coppia di questo tipo forma necessariamente un ciclo insieme a un qualsiasi terzo vertice. Un albero non può contenere cicli, quindi il verdetto è anche "NO".