시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWM2ZDBcdWMxMmRcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YmMxNVx1YzJhNFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVhZDZjXHVjMmFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAxXHVhYzFjXHViODVjIFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWJjMTVcdWMyYTRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzJhYyBcdWQ1NThcdWIwOThcdWI5N2MgXHVjNzc4XHVjODExXHVkNTVjIFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM2MmVcdWFlMzBcdWIyOTQgXHVhYzgzXHVjNzc0IFx1ZDU1YyBcdWJjODggXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWNkMWQgXHViYTg3IFx1YmM4OCBcdWM2YzBcdWM5YzFcdWM3NzRcdWJhNzQgXHViYWE4XHViNGUwIFx1YmMxNVx1YzJhNFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVhZDZjXHVjMmFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCAxXHVhYzFjXHVhYzAwIFx1YjQxOFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgblx1Yzc0MCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4IHZcdWM3NzRcdWIyZTQuIHZcdWIyZTRcdWM3NGNcdWM1ZDAgXHViMDk4XHVjNjI0XHViMjk0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWNjOThcdWM3NGNcdWM1ZDAgdlx1YzVkMCBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMjk0IFx1YmMxNVx1YzJhNFx1YzVkMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzJhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWFjZTAsIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHViMDk4XHVjNjI0XHViMjk0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM3OTBcdWMyZGRcdWM3NTggXHVjMjE4IGRcdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBkXHVhYzFjIFx1YzIyYlx1Yzc5MFx1YjI5NCB2XHVjNzU4IFx1Yzc5MFx1YzJkZCBcdWJjODhcdWQ2MzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPm4gPSAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM3ODVcdWI4MjVcdWM3NzQgXHViMDVkXHViMDk4XHViYTcwLCBcdWM3NzQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YjJmNVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjNzg1XHViODI1XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViYWE4XHViNGUwIFx1YmMxNVx1YzJhNFx1YzVkMCBcdWFkNmNcdWMyYWNcdWM3NDQgXHVkNTVjIFx1YWMxY1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjNmMwXHVjOWMxXHVjNzg0IFx1ZDY5Zlx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQzMTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYXJibGVzIG9uIGEgdHJlZSIsImRlc2NyaXB0aW9uIjoiPHA+biBib3hlcyBhcmUgcGxhY2VkIG9uIHRoZSB2ZXJ0aWNlcyBvZiBhIHJvb3RlZCB0cmVlLCB3aGljaCBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIG4sIDEgJmxlOyBuICZsZTsgMTAwMDAuIEVhY2ggYm94IGlzIGVpdGhlciBlbXB0eSBvciBjb250YWlucyBhIG51bWJlciBvZiBtYXJibGVzOyB0aGUgdG90YWwgbnVtYmVyIG9mIG1hcmJsZXMgaXMgbi48XC9wPlxyXG5cclxuPHA+VGhlIHRhc2sgaXMgdG8gbW92ZSB0aGUgbWFyYmxlcyBzdWNoIHRoYXQgZWFjaCBib3ggY29udGFpbnMgZXhhY3RseSBvbmUgbWFyYmxlLiBUaGlzIGlzIHRvIGJlIGFjY29tcGxpc2hlZCBiZSBhIHNlcXVlbmNlIG9mIG1vdmVzOyBlYWNoIG1vdmUgY29uc2lzdHMgb2YgbW92aW5nIG9uZSBtYXJibGUgdG8gYSBib3ggYXQgYW4gYWRqYWNlbnQgdmVydGV4LiBXaGF0IGlzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtb3ZlcyByZXF1aXJlZCB0byBhY2hpZXZlIHRoZSBnb2FsPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIGEgbnVtYmVyIG9mIGNhc2VzLiBFYWNoIGNhc2Ugc3RhcnRzIHdpdGggdGhlIG51bWJlciBuIGZvbGxvd2VkIGJ5IG4gbGluZXMuIEVhY2ggbGluZSBjb250YWlucyBhdCBsZWFzdCB0aHJlZSBudW1iZXJzIHdoaWNoIGFyZTogdiB0aGUgbnVtYmVyIG9mIGEgdmVydGV4LCBmb2xsb3dlZCBieSB0aGUgbnVtYmVyIG9mIG1hcmJsZXMgb3JpZ2luYWxseSBwbGFjZWQgYXQgdmVydGV4IHYgZm9sbG93ZWQgYnkgYSBudW1iZXIgZCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGNoaWxkcmVuIG9mIHYsIGZvbGxvd2VkIGJ5IGQgbnVtYmVycyBnaXZpbmcgdGhlIGlkZW50aXRpZXMgb2YgdGhlIGNoaWxkcmVuIG9mIHYuPFwvcD5cclxuXHJcbjxwPlRoZSBpbnB1dCBpcyB0ZXJtaW5hdGVkIGJ5IGEgY2FzZSB3aGVyZSBuID0gMCBhbmQgdGhpcyBjYXNlIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGNhc2UgaW4gdGhlIGlucHV0LCBvdXRwdXQgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBtb3ZlcyBvZiBtYXJibGVzIHJlc3VsdGluZyBpbiBvbmUgbWFyYmxlIGF0IGVhY2ggdmVydGV4IG9mIHRoZSB0cmVlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=