404030 - 网络巡视2

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

Input

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

Output

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

Examples

Input

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)

Output

1
2

Hint

第一组样例描述的树如图

Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题