Se dan enteros $n, m > 0$, así como enteros $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$. Construye un árbol $T$ con $n$ vértices $V = \{v_1, v_2, \dots, v_n\}$ con la siguiente condición: para cada vértice $v_i$ donde $a_i \ne -1$, el resto del grado $\deg_T(v_i)$ al dividirlo por $m$ debe ser igual a $a_i$. Si $a_i = -1$, entonces no hay restricciones sobre el grado de $v_i$.
Entrada
La primera línea de la entrada contiene un entero $t$, el número de casos de prueba ($1 \le t \le 5 \cdot 10^5$). Para cada caso de prueba:
La primera línea contiene dos enteros, $n$ y $m$, que indican el número de vértices en el árbol y el módulo ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$).
La siguiente línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ que indican los restos requeridos ($-1 \le a_i < m$).
La suma de $n$ en todos los casos de prueba no supera $5 \cdot 10^5$.
Salida
Para cada caso de prueba, si existe dicho árbol con $n$ vértices, imprime "YES" (en mayúsculas o minúsculas), seguido de $n - 1$ líneas con dos enteros cada una que indiquen los extremos de cada arista. En caso contrario, imprime "NO" (en mayúsculas o minúsculas).
Ejemplo
Entrada
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
Salida
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
En el primer caso de prueba, se nos pide construir un árbol con $n = 1$ vértice, $m = 5$ y arreglo de restos de grados $b = [0]$. Con un solo vértice, no puede haber aristas, por lo que hay exactamente un árbol posible: un único vértice de grado $0$. Como $0 \bmod 5 = 0$, cumple el requisito; por lo tanto, la respuesta es "YES".
En el segundo caso de prueba, necesitamos un árbol en $n = 2$ vértices con $m = 3$ y restos $b = [1, 1]$, lo que significa que ambos grados deben ser congruentes con $1$ módulo $3$. En dos vértices, solo hay un árbol: la única arista $1-2$. Sus grados son $(1, 1)$ y, en efecto, $1 \bmod 3 = 1$, por lo que la respuesta es "YES", e imprimir "1 2" es válido.
En el tercer caso de prueba, necesitamos $n = 5$, $m = 4$, con restos $b = [0, 1, 1, 1, 1]$: el primer vértice debe tener grado divisible por $4$, mientras que los otros cuatro vértices deben tener $\text{degree} \equiv 1 \pmod 4$. Una construcción natural es una estrella centrada en el vértice $1$: conectar $1$ con todos los demás vértices. Entonces $\deg(1) = 4$ y $4 \bmod 4 = 0$, mientras que cada uno de $2, 3, 4, 5$ tiene grado $1$ y $1 \bmod 4 = 1$. Por lo tanto, la respuesta es "YES", y las aristas "1 2", "1 3", "1 4", "1 5" funcionan.
En el cuarto caso de prueba, necesitamos un árbol con $n = 6$, $m = 2$, restos $b = [1, 0, 0, 0, 0, 1]$, es decir, los extremos deben tener grado impar y los cuatro vértices centrales deben tener grado par. Módulo $2$, esto es puramente una restricción de paridad. El camino simple $1-2-3-4-5-6$ encaja perfectamente: los vértices $1$ y $6$ tienen grado $1$ (impar), y los vértices $2, 3, 4, 5$ tienen grado $2$ (par). Por consiguiente, la respuesta es "YES", y las aristas del camino son correctas.
En el quinto caso de prueba, se nos pide construir un grafo (y por tanto, en particular, un árbol) en $n = 3$ con $m = 2$ y $b = [1, 1, 1]$, de modo que cada vértice debe tener grado impar. Esto es imposible: en todo grafo no dirigido, el número de vértices de grado impar es siempre par, por lo que tener tres grados impares no puede ocurrir para ningún conjunto de aristas. Por lo tanto, el veredicto es "NO".
En el sexto caso de prueba, tenemos $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$. Como $m > n - 1 = 3$, el resto módulo $10$ es igual al propio grado, por lo que requerimos exactamente $\deg = [3, 3, 1, 1]$. Eso obliga a dos vértices a ser adyacentes a todos los demás (grado $3$ en un grafo de $4$ vértices), y cuando $n > 2$, cualquier par de este tipo forma necesariamente un ciclo junto con cualquier tercer vértice. Un árbol no puede contener ciclos, por lo que el veredicto también es "NO".