No submission language available for this problem.

Background

Special for beginners, ^_^

Description

Bob 喜欢玩战略游戏，但他有时找不到足够快的解决方案。现在他必须包围一座中世纪城市，城市的道路形成一棵树。他必须把最小数量的士兵放在结点上，这样才可以观察到所有道路。

请帮助 Bob 找到放置的最小士兵数。例如，对下图所示的树，解决方案是放置 1 个士兵（放置在结点 1 处）。

Format

Input

输入有多个测试用例。

每个测试用例的第 1 行都包含结点数 $n \in (0,1500]$;

接下来的 $n$ 行，每行的描述格式都为 "结点编号:(道路数)结点编号1 结点编号2 结点编号3..." 或 "结点编号:(0)"。

结点编号为 $0$~$n-1$, 每个结点链接的道路都不超过 10 条。每条道路在输入数据中都只出现一次。

Output

针对每个测试用例，都单行输出放置的最小士兵数量

Samples

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

Limitation

1s, 1024KiB for each test case.