Hide

# Problem GMarbles On A Tree

$n$ boxes are placed on the vertices of a rooted tree, which are numbered from $1$ to $n$, $1 \le n \le 10\, 000$. Each box is either empty or contains a number of marbles; the total number of marbles is $n$.

The task is to move the marbles such that each box contains exactly one marble. This is to be accomplished be a sequence of moves; each move consists of moving one marble to a box at an adjacent vertex. What is the minimum number of moves required to achieve the goal?

## Input

The input contains up to $10$ cases. Each case starts with the number $n$ followed by $n$ lines. Each line contains at least three numbers which are:

• $1 \le v \le n$, the number of a vertex. The vertices are numbered from $1$ to $n$ and are given in increasing order in the input.

• $0 \le m \le n$, the number of marbles originally placed at vertex $v$.

• $0 \le d \le n-1$, the number of children of $v$.

Then (on the same line) follow $d$ distinct vertex numbers giving the identities of the children of $v$.

The input is terminated by a case where $n = 0$ and this case should not be processed.

## Output

For each case in the input, output the smallest number of moves of marbles resulting in one marble at each vertex of the tree.

Sample Input 1 Sample Output 1
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

7
14
20