Código acm.uva.es: 10672
 Canicas en el árbol  
En los nodos de un árbol se colocan n cajas, numeradas desde 1 hasta n, con 1 ≤ n ≤ 10000. Cada caja puede estar vacía o contener cierta cantidad de canicas; el número total de canicas es n.

Tu tarea es mover las canicas de manera que cada caja contenga exactamente una canica. Esto se hace con una serie de movimientos, donde cada movimiento consiste en mover una canica a una caja adyacente (es decir, a un nodo hijo o padre). ¿Cuál es el número mínimo de movimientos para conseguir el objetivo?

Entrada

La entrada puede contener varios casos de prueba. Cada caso empieza con el número de nodos, n, seguido de n líneas. Cada línea contiene al menos 3 números que son: v el número del vértice, el número de canicas colocadas inicialmente en ese vértice, seguido de un número d que indica el número de hijos de v, y finalmente vienen d números con las identidades de los hijos de v.

La entrada acaba con un caso donde n = 0. Este caso no debe ser procesado.

Salida

Para cada caso de entrada, la salida debe ser el menor número de movimientos de canicas para colocar una canica en cada nodo del árbol.

Ejemplo de entrada

9
1 2 3 2 3 4
2 1 0
3 0 2 5 6
4 1 3 7 8 9
5 3 0
6 0 0
7 0 0
8 2 0
9 0 0
9
1 0 3 2 3 4
2 0 0
3 0 2 5 6
4 9 3 7 8 9
5 0 0
6 0 0
7 0 0
8 0 0
9 0 0
9
1 0 3 2 3 4
2 9 0
3 0 2 5 6
4 0 3 7 8 9
5 0 0
6 0 0
7 0 0
8 0 0
9 0 0
0

Ejemplo de salida

7
14
20