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