Bob enjoys playing computer games, especially strategic games, but sometimes he cannot find the solution fast enough and then he is very sad. Now he has the following problem. He must defend a medieval city, the roads of which form a tree. He has to put the minimum number of soldiers on the nodes so that they can observe all the edges. Can you help him?

Your program should find the minimum number of soldiers that Bob has to put for a given tree.

The input file contains several data sets in text format. Each data set represents a tree with the following description:

the number of nodes
the description of each node in the following format
node_identifier:(number_of_roads) node_identifier1 node_identifier2 ... node_identifier
or
node_identifier:(0)

The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500). Every edge appears only once in the input data.

For example for the tree:

the solution is one soldier ( at the node 1).

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the minimum number of soldiers). An example is given in the following table:

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

题意：给出树的结点之间的关系,如1:(2) 2 3 ，表示2和3的父亲都是1.在1点设点，则其邻接点2和3都可被覆盖，求出最少要多少个点才能覆盖整棵树。即最小顶点覆盖。

分析：树的各点之间只有一条边，而且树明显的特性是有层次的数据结构。f[u][0]表示以u为根且u不加入覆盖集的最小顶点覆盖，f[u][1]表示以u为根且u加入覆盖集的最小顶点覆盖。每个点都有两个状态，就是加入与不加入覆盖集。

最优子结构：要知道f[u][0]=只需知道u的子节点个数；要知道f[u][1]，则要知道分别以u的孩子v们为根的最小顶点覆盖，对这种情况，每个孩子可加入也可不加入覆盖集（取最优的），以为树有层次，所以要知道根部，就要知道孩子的最小顶点覆盖，孩子的最小顶点覆盖跟父亲没有关系。

子问题重叠：这里没有子问题重叠。

边界问题：每个节点对应两种边界问题，即当处理一个节点是，有取和不取两种情况。

子问题独立：对于u的孩子v1，v2：v1的孩子跟v2的孩子毫无关系。这种性质延伸到u的所有孩子上，即每个孩子的解互相没有关系。

代码：