Gitt er heltall $n, m > 0$, samt heltall $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$. Konstruer et tre $T$ med $n$ noder $V = \{v_1, v_2, \dots, v_n\}$ med følgende betingelse: for hver node $v_i$ der $a_i \ne -1$, må resten når graden $\deg_T(v_i)$ deles på $m$ være lik $a_i$. Hvis $a_i = -1$, er det ingen begrensninger på graden til $v_i$.

Inndata

Den første linjen i inndataene inneholder et heltall $t$, antallet testtilfeller ($1 \le t \le 5 \cdot 10^5$). For hvert testtilfelle:

Den første linjen inneholder to heltall, $n$ og $m$, som angir antallet noder i treet og modulen ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$).

Den neste linjen inneholder $n$ heltall $a_1, a_2, \dots, a_n$ som angir de påkrevde restene ($-1 \le a_i < m$).

Summen av $n$ over alle testtilfeller overstiger ikke $5 \cdot 10^5$.

Utdata

For hvert testtilfelle, hvis et slikt tre med $n$ noder finnes, skriv ut «YES» (uansett store/små bokstaver), etterfulgt av $n - 1$ linjer med to heltall hver som angir endepunktene for hver kant. Ellers, skriv ut «NO» (uansett store/små bokstaver).

Eksempel

Inndata

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

Utdata

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

Merk

I det første testtilfellet blir vi bedt om å bygge et tre med $n = 1$ node, $m = 5$ og gradrest-tabell $b = [0]$. Med bare én node kan det ikke være noen kanter, så det finnes nøyaktig ett mulig tre: en enkelt node med grad $0$. Siden $0 \bmod 5 = 0$, oppfyller det kravet; dermed er svaret «YES».

I det andre testtilfellet trenger vi et tre på $n = 2$ noder med $m = 3$ og rester $b = [1, 1]$, som betyr at begge gradene må være kongruente med $1$ modulo $3$. På to noder finnes det bare ett tre: den ene kanten $1-2$. Gradene er $(1, 1)$ og $1 \bmod 3 = 1$, så svaret er «YES», og å skrive ut «1 2» er gyldig.

I det tredje testtilfellet trenger vi $n = 5$, $m = 4$, med rester $b = [0, 1, 1, 1, 1]$: den første noden må ha grad delelig med $4$, mens de fire andre nodene må ha $\text{degree} \equiv 1 \pmod 4$. En naturlig konstruksjon er en stjerne med sentrum i node $1$: koble $1$ til hver av de andre nodene. Da er $\deg(1) = 4$ og $4 \bmod 4 = 0$, mens hver av $2, 3, 4, 5$ har grad $1$ og $1 \bmod 4 = 1$. Derfor er svaret «YES», og kantene «1 2», «1 3», «1 4», «1 5» fungerer.

I det fjerde testtilfellet trenger vi et tre med $n = 6$, $m = 2$, rester $b = [1, 0, 0, 0, 0, 1]$, dvs. at endepunktene må ha odde grad og de fire midterste nodene må ha partallsgrad. Modulo $2$ er dette kun et paritetskrav. Den enkle stien $1-2-3-4-5-6$ passer perfekt: nodene $1$ og $6$ har grad $1$ (odde), og nodene $2, 3, 4, 5$ har grad $2$ (partall). Dermed er svaret «YES», og kantene på stien er korrekte.

I det femte testtilfellet blir vi bedt om å bygge en graf (og dermed spesielt et tre) på $n = 3$ med $m = 2$ og $b = [1, 1, 1]$, slik at hver node må ha odde grad. Dette er umulig: i enhver urettet graf er antallet noder med odde grad alltid et partall, så tre odde grader kan ikke forekomme for noen mengde kanter. Derfor er svaret «NO».

I det sjette testtilfellet har vi $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$. Siden $m > n - 1 = 3$, er resten modulo $10$ lik selve graden, så vi krever nøyaktig $\deg = [3, 3, 1, 1]$. Det tvinger to noder til å være naboer med alle andre (grad $3$ i en graf med $4$ noder), og når $n > 2$, vil ethvert slikt par nødvendigvis danne en sykel sammen med en hvilken som helst tredje node. Et tre kan ikke inneholde sykler, så svaret er også «NO».