题目描述

题目翻译

给定一棵 $n$ 个节点的树。你需要让这棵树上的每条边都被看守。当一条边的端点上至少有一个士兵时，我们就说这条边被看守。求出看守这棵树最少用的士兵数量。

输入格式

本题有不定组数的多组数据。

对于每组数据，第一行为正数 $n$，描述树的大小。

请注意节点编号从 $0$ 开始，

接下来 $n$ （$0< n \leq 1500$） 行中，每行可能为：

• $u_i:(k_i)$ $v_1$ $v_2$ $\cdots$ $v_{k_i}$

u_i:(k_i) v_1 v_2 ... v_{k_i}

表示点 $u_i$ 的儿子有 $k_i$ 个，编号依次为 $v_1,v_2,\cdots,v_{k_i}$；

也可能为

• $u_i:(0)$

u_i:(0)

表示点 $u_i$ 没有儿子。

输出格式

对于每组数据，输出一行一个整数，即答案。

输入输出样例 #1

输入 #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