시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 47 18 16 50.000%

문제

루트가 있는 트리의 정점 위에 박스 N개가 놓여져 있다. 각 정점은 1부터 n까지 번호가 매겨져 있으며, 1 ≤ n ≤ 10000이다. 박스는 구슬을 몇 개 포함하고 있거나 비어있다. 구슬의 총 개수는 n이다.

원섭이는 모든 박스에 들어있는 구슬의 개수를 1개로 만드려고 한다. 한 박스에 들어있는 구슬 하나를 인접한 정점으로 옮기는 것이 한 번 움직이는 것이다. 이 때, 총 몇 번 움직이면 모든 박스에 들어있는 구슬의 개수가 1개가 되는지 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n이 주어지며, n은 정점의 개수이다. 다음 n개 줄에는 각 정점의 정보가 주어진다. 첫 번째 숫자는 정점의 번호 v이다. v다음에 나오는 숫자는 처음에 v에 놓여져 있는 박스에 들어 있는 구슬의 개수이고, 그 다음에 나오는 숫자는 자식의 수 d이다. 다음 d개 숫자는 v의 자식 번호이다.

n = 0인 경우에 입력이 끝나며, 이 경우는 답을 구하면 안된다.

출력

각각의 입력에 대해서, 모든 박스에 구슬을 한 개로 만드는 움직임 횟수의 최소값을 출력한다.

예제 입력

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

힌트