Annetaan kokonaisluvut $n, m > 0$ sekä kokonaisluvut $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$. Muodosta $n$-solmuinen puu $T$, jonka solmujoukko on $V = \{v_1, v_2, \dots, v_n\}$ ja joka toteuttaa seuraavan ehdon: jokaiselle solmulle $v_i$, jolle $a_i \ne -1$, asteiden $\deg_T(v_i)$ jakojäännöksen luvulla $m$ jaettaessa täytyy olla $a_i$. Jos $a_i = -1$, solmun $v_i$ asteelle ei ole rajoituksia.

Syöte

Syötteen ensimmäinen rivi sisältää kokonaisluvun $t$, testitapausten lukumäärän ($1 \le t \le 5 \cdot 10^5$). Jokaiselle testitapaukselle:

Ensimmäinen rivi sisältää kaksi kokonaislukua, $n$ ja $m$, jotka ilmaisevat puun solmujen lukumäärän ja jakajan ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$).

Seuraava rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$, jotka ilmaisevat vaaditut jakojäännökset ($-1 \le a_i < m$).

Lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $5 \cdot 10^5$.

Tuloste

Jokaiselle testitapaukselle, jos tällainen $n$-solmuinen puu on olemassa, tulosta "YES" (kirjainkoosta riippumatta) ja sen jälkeen $n - 1$ riviä, joista jokaisella on kaksi kokonaislukua, jotka ilmaisevat kunkin kaaren päätepisteet. Muussa tapauksessa tulosta "NO" (kirjainkoosta riippumatta).

Esimerkki

Syöte

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

Tuloste

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

Huomautus

Ensimmäisessä testitapauksessa meitä pyydetään rakentamaan puu, jossa on $n = 1$ solmu, $m = 5$ ja asteiden jakojäännöstaulukko $b = [0]$. Kun solmuja on vain yksi, kaaria ei voi olla, joten mahdollisia puita on täsmälleen yksi: yksittäinen solmu, jonka aste on $0$. Koska $0 \bmod 5 = 0$, se täyttää vaatimuksen; vastaus on siis "YES".

Toisessa testitapauksessa tarvitsemme puun $n = 2$ solmulle, kun $m = 3$ ja jakojäännökset ovat $b = [1, 1]$, mikä tarkoittaa, että molempien asteiden on oltava kongruentteja luvun $1$ kanssa modulo $3$. Kahdella solmulla on vain yksi puu: yksittäinen kaari $1-2$. Sen asteet ovat $(1, 1)$ ja todellakin $1 \bmod 3 = 1$, joten vastaus on "YES", ja "1 2" on kelvollinen tuloste.

Kolmannessa testitapauksessa tarvitsemme $n = 5$, $m = 4$ ja jakojäännökset $b = [0, 1, 1, 1, 1]$: ensimmäisen solmun asteen on oltava jaollinen luvulla $4$, kun taas muiden neljän solmun on toteutettava ehto $\text{degree} \equiv 1 \pmod 4$. Luonnollinen rakenne on tähtiverkko, jonka keskus on solmu $1$: yhdistetään $1$ jokaiseen muuhun solmuun. Tällöin $\deg(1) = 4$ ja $4 \bmod 4 = 0$, kun taas jokaisella solmuista $2, 3, 4, 5$ on aste $1$ ja $1 \bmod 4 = 1$. Vastaus on siis "YES", ja kaaret "1 2", "1 3", "1 4", "1 5" kelpaavat.

Neljännessä testitapauksessa tarvitsemme puun, jossa $n = 6$, $m = 2$ ja jakojäännökset $b = [1, 0, 0, 0, 0, 1]$, eli päätepisteillä on oltava pariton aste ja neljällä keskimmäisellä solmulla parillinen aste. Modulo $2$ tämä on pelkkä pariteettirajoite. Yksinkertainen polku $1-2-3-4-5-6$ sopii täydellisesti: solmujen $1$ ja $6$ aste on $1$ (pariton), ja solmujen $2, 3, 4, 5$ aste on $2$ (parillinen). Vastaus on siis "YES", ja polun kaaret ovat oikein.

Viidennessä testitapauksessa meitä pyydetään rakentamaan verkko (ja siten erityisesti puu) $n = 3$ solmulle, kun $m = 2$ ja $b = [1, 1, 1]$, joten jokaisella solmulla on oltava pariton aste. Tämä on mahdotonta: jokaisessa suuntaamattomassa verkossa paritonasteisten solmujen lukumäärä on aina parillinen, joten kolmea paritonta astetta ei voi esiintyä millään kaarijoukolla. Tuomio on siis "NO".

Kuudennessa testitapauksessa meillä on $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$. Koska $m > n - 1 = 3$, jakojäännös modulo $10$ on yhtä suuri kuin itse aste, joten vaadimme täsmälleen asteet $\deg = [3, 3, 1, 1]$. Tämä pakottaa kaksi solmua olemaan kaikkien muiden naapureita (aste $3$ $4$-solmuisessa verkossa), ja kun $n > 2$, mikä tahansa tällainen pari muodostaa väistämättä syklin yhdessä minkä tahansa kolmannen solmun kanssa. Puu ei voi sisältää syklejä, joten tuomio on myös "NO".