题目描述
鲍勃喜欢玩战略游戏，但他有时找不到足够快的解决方案。现在他必须保卫一座中世纪城市，城市的道路形成一棵树。他必须把最小数量的士兵放在节点上，这样才可以观察到所有道路。请帮助鲍勃找到放置的最小士兵数。例如，对如下图所示的树，解决方案是放置1个士兵（放置在节点1处）。
输入
输入多个测试用例。每个测试用例的第1行都包含节点数n（0<n ≤1500）；接下来的n 行，每行的描述格式都为“节点编号：（道路数）节点编号1节点编号2…”或“节点编号：(0)”。节点编号为0～n -1，每个节点连接的道路数都不超过10条。每条道路在输入数据中都只出现一次。
输出
对每个测试用例，都单行输出放置的最小士兵数。
样例输入 Copy
4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)
样例输出 Copy
1
2