404030 - 网络巡视2

通信公司的网络各结点构成了一棵树，为了防止破坏，需要在一些结点安置巡视岗，安置巡视岗的结点不仅可以看到相邻结点的情况，还可以看到结点之间的道路情况。 请问最少需要安置多少个岗位。

输入

输入包括多组数据，每组数据第一行一个整数n (0＜n≤1 500)表示树的结点数。随后n行依次描述各结点之间的关系。

输出

每组数据输出一个整数，即最少安置数。

样例

输入

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
2

提示

第一组样例描述的树如图

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题