En LeetCode se pide una copia profunda de un grafo: crear un nodo nuevo por cada nodo original y conectar los nuevos igual que los originales,. Aquí el recorrido queda a la vista, porque la copia numera sus nodos en el orden en que se crean.

El grafo es no dirigido y conexo, con nodos \(1, \dots, n\); cada nodo tiene su lista de vecinos en un orden dado. La copia se construye con un BFS desde el nodo \(1\):

• La copia del nodo \(1\) se crea primero y recibe el número \(1\).
• Al procesar un nodo (en el orden de la cola), se recorren sus vecinos en el orden de su lista; cada vecino que todavía no tiene copia recibe el siguiente número y entra a la cola.

Imprime las listas de vecinos de la copia.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 10^5)\). La \(i\)-ésima de las siguientes \(n\) líneas describe al nodo \(i\): primero su cantidad de vecinos \(d_i\) y luego los vecinos en orden. No hay lazos ni aristas repetidas, si \(j\) está en la lista de \(i\) entonces \(i\) está en la de \(j\), el grafo es conexo y \(\sum d_i \le 4 \cdot 10^5\).

Salida

\(n\) líneas: la \(i\)-ésima describe al nodo \(i\) de la copia, con su cantidad de vecinos seguida de los números (de la copia) de sus vecinos, en el mismo orden que la lista original.

Ejemplo 1

Entrada

4
2 2 4
2 1 3
2 2 4
2 1 3

Salida

2 2 3
2 1 4
2 1 4
2 2 3

Ejemplo 2

Entrada

3
1 3
1 3
2 2 1

Salida

1 2
2 3 1
1 2

Ejemplo 3

Entrada

1
0

Salida

0

Basado en el problema 133 de LeetCode, Clone Graph, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.