描述 鲍勃喜欢玩电脑游戏，尤其是策略游戏，但有时他无法快速找到解决方案，这时他会非常沮丧。现在他面临以下问题。他必须保卫一座中世纪城市，城市的道路构成一棵树。他必须在节点上放置最少数量的士兵，以便他们能够监视所有的边。你能帮助他吗？

你的程序应该为给定的树找到鲍勃必须放置的最少士兵数量。

例如对于这棵树：

解决方案是一名士兵（在节点1上）。

输入 输入包含若干文本格式的数据集。每个数据集表示一棵树，其描述如下：

• 节点数量
• 每个节点的描述采用以下格式：

节点标识符:(道路数量) 节点标识符1 节点标识符2 … 节点标识符道路数量

或者

节点标识符:(0)

节点标识符是介于0和n - 1之间的整数（对于n个节点，$0 < n \leq 1500$）；输入的每一行中的道路数量不超过10。每条边在输入数据中只出现一次。

输出 输出应该打印在标准输出上。对于每个给定的输入数据集，在单独的一行中打印一个整数，表示结果（最少士兵数量）。下面给出一个示例：

输入数据 1

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)

输出数据 1

1
2

来源 2000年东南欧竞赛