En general, una criptomoneda basada en Tangle funciona así. Hay un grafo dirigido acíclico (DAG) que llamamos Tangle. Su red está compuesta por nodos, entidades que emiten y validan transacciones. Las transacciones emitidas constituyen el conjunto de vértices del grafo Tangle, el registro que las almacena. Su conjunto de aristas se obtiene así: cuando llega una nueva transacción $X$, debe aprobar dos anteriores. Estas aprobaciones se representan por aristas dirigidas, como en la figura 4(a). Si no hay una arista dirigida entre las transacciones $A$ y $G$, pero hay un camino dirigido de longitud al menos dos de $A$ a $G$, decimos que $A$ aprueba indirectamente a $G$. En la figura 4(a), $A$ aprueba directamente a $B$ y $D$, e indirectamente a $F$, $G$, $H$ e $I$. Definimos los “Tips” como transacciones no aprobadas en el grafo Tangle. En la instantánea de la figura 4(a), los Tips son $A$ y $C$. Cuando llega $X$ y aprueba a $A$ y $C$ en la instantánea de la figura 4(b), $X$ se convierte en el único Tip.

Figura 4: Un grafo Tangle con pesos antes y después de emitir una nueva transacción $X$. Las cajas representan transacciones; el número pequeño de la esquina inferior derecha (sureste, SE) de cada caja indica el peso propio y el número en negrita indica el peso acumulado.

Definimos el peso de una transacción y conceptos relacionados. El peso es proporcional al trabajo que su nodo emisor invirtió en ella. Lo único importante es que cada transacción lleva asociado un entero positivo, su peso. En general, la idea es que una transacción con mayor peso es más “importante” que una de menor peso. Supongamos que $X$ tiene un peso propio $W_X$, donde $1 \le W_X \le W_{\max}$. Su peso acumulado $CW_X$ es la suma de su peso y de los pesos de todas las transacciones que la aprueban directa o indirectamente. La figura 4 ilustra su cálculo. Las cajas representan transacciones; el número pequeño de la esquina inferior derecha es el peso propio y el número en negrita es el acumulado. Por ejemplo, las transacciones $A$, $B$, $C$ y $E$ aprueban directa o indirectamente a $F$.

El peso acumulado de $F$ es $CW_F=3+1+3+1+1=9$, la suma del peso propio de $F$ y los pesos de $A$, $B$, $C$ y $E$, respectivamente. Tras la aprobación de la nueva transacción $X$ ($W_X=3$), el peso acumulado de todas las demás aumenta en $3$. El peso acumulado mide el esfuerzo computacional que respalda la transacción. Al alcanzar un umbral $TH$, se marca como confirmada, pues la probabilidad de una modificación maliciosa es baja. En otras palabras, al recibir aprobaciones adicionales, el sistema la acepta con mayor confianza. Las transacciones aprobadas con peso acumulado menor que el límite superior se llaman no confirmadas. Si $TH=12$, las transacciones $F$, $G$, $H$ e $I$ de la figura 4 están confirmadas. Al inicio de Tangle había una dirección cuyo saldo contenía todos los tokens. La transacción Genesis los envió a varias direcciones “fundadoras”. Todos los tokens se crearon en Genesis. Por tanto, todas las demás transacciones aprueban a Genesis directa o indirectamente (figura 5). Inicialmente, al crear una transacción, un nodo selecciona dos Tips (transacciones no aprobadas) mediante un algoritmo de selección de Tips. Cada nueva transacción debe aprobar dos anteriores, representadas por aristas dirigidas. Los demás nodos la verifican y la añaden como un nuevo Tip al DAG. Al añadirse como Tip, no está aprobada. Cuando una transacción posterior selecciona ese Tip, pasa a estar aprobado. El peso acumulado asociado a una transacción se actualiza cada vez que otra la aprueba directa o indirectamente.

Figura 5: Un grafo Tangle con pesos asignados a cada transacción

Por comodidad, el Tangle inicial se muestra en la figura 6(a). Una nueva transacción $X$ selecciona dos Tips $Y$ y $Z$ (transacciones no aprobadas) mediante un algoritmo de selección de Tips. La figura 6(b) muestra las notaciones de los pesos y los pesos acumulados de $X$, $Y$ y $Z$, respectivamente.

(a) El Tangle inicial. (b) $X$ aprueba a $Y$ y $Z$. Figura 6: Un grafo Tangle con pesos asignados a cada transacción

Figura 7: El grafo Tangle de la entrada de ejemplo 1, donde $TH=12$ ($CW_X \ge TH$ para $T_2$ y $T_3$).

Entrada

La primera línea contiene un par de enteros $n$, $TH$, donde $n$ indica la cantidad de transacciones y $TH$ el umbral del peso acumulado. Las transacciones se dan en orden creciente de $X$. Cada una ocupa una línea con una lista de enteros $X$, $Y$, $Z$, $W_X$, donde $2 \le X \le 10000$, $0 \le Y,Z \le X-1$, $Y \ne Z$ y $1 \le W_X \le 5$.

Restricciones

• $1 \le n \le 10000$
• $2 \le X \le n+1$
• $0 \le Y,Z \le X-1$, $Y \ne Z$

Salida

Tras procesar las $n$ transacciones, para una transacción $T_X$ en $\{T_2,T_3,\ldots,T_n\}$ con $CW_X \ge TH$, imprime la lista de valores $X$, $CW_X$ en orden creciente de $X$. Cada línea contiene una transacción. Finalmente imprime la cantidad total de transacciones confirmadas.

Ejemplos

Entrada 1

6 12
2 0 1 3
3 0 2 2
4 1 2 1
5 2 3 3
6 3 4 4
7 3 5 5

Salida 1

2 18
3 14
2