Marbles on a Tree

Time limit1sMemory limit128 MB

Summary

Given a rooted tree where each vertex has a box and the total marbles equal the number of vertices, find the minimum number of moves (along edges) so every box holds exactly one marble.

Level: Medium6 of 10
Topics: Tree, DFS, Greedy, Dynamic programming
Solved: No attempts yet

Problem

A box sits on each vertex of a rooted tree. The vertices are numbered from $1$ to $n$ , where $1 \le n \le 10000$ . Each box holds some marbles or is empty, and the total number of marbles placed across the whole tree is exactly $n$ .

A single move takes one marble out of a box and places it into the box on an adjacent vertex (its parent or one of its children). Write a program that computes the minimum number of moves needed so that every box holds exactly one marble.

Input

The input consists of several test cases. The first line of each test case contains the number of vertices $n$ . Each of the next $n$ lines describes one vertex: the vertex number $v$ , the number of marbles initially in the box at $v$ , and the number of children $d$ of $v$ , followed by the $d$ child numbers of $v$ .

A line containing $n = 0$ marks the end of the input and must not be processed.

Output

For each test case, print on its own line the minimum number of moves required to leave exactly one marble in every box.

Examples7

Example 1

Input

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

Expected output

7
14
20

Example 2
Input
```
1
1 1 0
0
```
Expected output
```
0
```
Example 3
Input
```
2
1 2 1 2
2 0 0
0
```
Expected output
```
1
```
Example 4
Input
```
3
1 0 1 2
2 0 1 3
3 3 0
0
```
Expected output
```
3
```
Example 5
Input
```
4
1 1 3 2 3 4
2 1 0
3 1 0
4 1 0
0
```
Expected output
```
0
```

Example 6

Input

5
1 5 4 2 3 4 5
2 0 0
3 0 0
4 0 0
5 0 0
0

Expected output

Example 7
Input
```
3
3 3 2 1 2
1 0 0
2 0 0
0
```
Expected output
```
2
```