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

문제

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

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

입력

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

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

출력

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

예제 입력 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

예제 출력 1

7
14
20
W3sicHJvYmxlbV9pZCI6IjQzMTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWJiMzQgXHVjNzA0XHVjNzU4IFx1YWQ2Y1x1YzJhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHViOGU4XHVkMmI4XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWQyYjhcdWI5YWNcdWM3NTggXHVjODE1XHVjODEwIFx1YzcwNFx1YzVkMCBcdWJjMTVcdWMyYTQgTlx1YWMxY1x1YWMwMCBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjODE1XHVjODEwXHVjNzQwIDFcdWJkODBcdWQxMzAgblx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgMSAmbGU7IG4gJmxlOyAxMDAwMFx1Yzc3NFx1YjJlNC4gXHViYzE1XHVjMmE0XHViMjk0IFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWJhODcgXHVhYzFjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWFjNzBcdWIwOTggXHViZTQ0XHVjNWI0XHVjNzg4XHViMmU0LiBcdWFkNmNcdWMyYWNcdWM3NTggXHVjZDFkIFx1YWMxY1x1YzIxOFx1YjI5NCBuXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2ZDBcdWMxMmRcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YmMxNVx1YzJhNFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVhZDZjXHVjMmFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAxXHVhYzFjXHViODVjIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWJjMTVcdWMyYTRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzJhYyBcdWQ1NThcdWIwOThcdWI5N2MgXHVjNzc4XHVjODExXHVkNTVjIFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM2MmVcdWFlMzBcdWIyOTQgXHVhYzgzXHVjNzc0IFx1ZDU1YyBcdWJjODggXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWNkMWQgXHViYTg3IFx1YmM4OCBcdWM2YzBcdWM5YzFcdWM3NzRcdWJhNzQgXHViYWE4XHViNGUwIFx1YmMxNVx1YzJhNFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVhZDZjXHVjMmFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCAxXHVhYzFjXHVhYzAwIFx1YjQxOFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgblx1Yzc0MCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4IHZcdWM3NzRcdWIyZTQuIHZcdWIyZTRcdWM3NGNcdWM1ZDAgXHViMDk4XHVjNjI0XHViMjk0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWNjOThcdWM3NGNcdWM1ZDAgdlx1YzVkMCBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMjk0IFx1YmMxNVx1YzJhNFx1YzVkMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzJhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWFjZTAsIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHViMDk4XHVjNjI0XHViMjk0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM3OTBcdWMyZGRcdWM3NTggXHVjMjE4IGRcdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBkXHVhYzFjIFx1YzIyYlx1Yzc5MFx1YjI5NCB2XHVjNzU4IFx1Yzc5MFx1YzJkZCBcdWJjODhcdWQ2MzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPm4gPSAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM3ODVcdWI4MjVcdWM3NzQgXHViMDVkXHViMDk4XHViYTcwLCBcdWM3NzQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YjJmNVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM3ODVcdWI4MjVcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWJhYThcdWI0ZTAgXHViYzE1XHVjMmE0XHVjNWQwIFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWQ1NWMgXHVhYzFjXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWM2YzBcdWM5YzFcdWM3ODQgXHVkNjlmXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDMxNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1hcmJsZXMgb24gYSB0cmVlIiwiZGVzY3JpcHRpb24iOiI8cD5uIGJveGVzIGFyZSBwbGFjZWQgb24gdGhlIHZlcnRpY2VzIG9mIGEgcm9vdGVkIHRyZWUsIHdoaWNoIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbiwgMSAmbGU7IG4gJmxlOyAxMDAwMC4gRWFjaCBib3ggaXMgZWl0aGVyIGVtcHR5IG9yIGNvbnRhaW5zIGEgbnVtYmVyIG9mIG1hcmJsZXM7IHRoZSB0b3RhbCBudW1iZXIgb2YgbWFyYmxlcyBpcyBuLjxcL3A+XHJcblxyXG48cD5UaGUgdGFzayBpcyB0byBtb3ZlIHRoZSBtYXJibGVzIHN1Y2ggdGhhdCBlYWNoIGJveCBjb250YWlucyBleGFjdGx5IG9uZSBtYXJibGUuIFRoaXMgaXMgdG8gYmUgYWNjb21wbGlzaGVkIGJlIGEgc2VxdWVuY2Ugb2YgbW92ZXM7IGVhY2ggbW92ZSBjb25zaXN0cyBvZiBtb3Zpbmcgb25lIG1hcmJsZSB0byBhIGJveCBhdCBhbiBhZGphY2VudCB2ZXJ0ZXguIFdoYXQgaXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzIHJlcXVpcmVkIHRvIGFjaGlldmUgdGhlIGdvYWw/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgYSBudW1iZXIgb2YgY2FzZXMuIEVhY2ggY2FzZSBzdGFydHMgd2l0aCB0aGUgbnVtYmVyIG4gZm9sbG93ZWQgYnkgbiBsaW5lcy4gRWFjaCBsaW5lIGNvbnRhaW5zIGF0IGxlYXN0IHRocmVlIG51bWJlcnMgd2hpY2ggYXJlOiB2IHRoZSBudW1iZXIgb2YgYSB2ZXJ0ZXgsIGZvbGxvd2VkIGJ5IHRoZSBudW1iZXIgb2YgbWFyYmxlcyBvcmlnaW5hbGx5IHBsYWNlZCBhdCB2ZXJ0ZXggdiBmb2xsb3dlZCBieSBhIG51bWJlciBkIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgY2hpbGRyZW4gb2YgdiwgZm9sbG93ZWQgYnkgZCBudW1iZXJzIGdpdmluZyB0aGUgaWRlbnRpdGllcyBvZiB0aGUgY2hpbGRyZW4gb2Ygdi48XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IGlzIHRlcm1pbmF0ZWQgYnkgYSBjYXNlIHdoZXJlIG4gPSAwIGFuZCB0aGlzIGNhc2Ugc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSBpbiB0aGUgaW5wdXQsIG91dHB1dCB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIG1vdmVzIG9mIG1hcmJsZXMgcmVzdWx0aW5nIGluIG9uZSBtYXJibGUgYXQgZWFjaCB2ZXJ0ZXggb2YgdGhlIHRyZWUuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==