题目描述

王老师正在玩一款淘汰游戏，他所在学校有N个教室，这N个教室和教室之间的道路正好构成一颗树，现在他需要在教室上放置鸡来淘汰连接该教室的道路，你的任务是帮助他找到用最少的方式鸡淘汰所有道路的方案。
例如下图就只需要一个鸡放在 1 号节点。

输入格式

输入文件中有多组数据，每组数据的第一行 N 表示点的个数。接下来 N 行每行格式如下：
x:(k) a1 a2 … ak（x 为点的编号，k 为与其相连的子节点个数，a1, a2, …, ak 分别为子节点的编号）

输出格式

对于每组数据输出一行一个数，即最少鸡数。

样例输入

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

数据范围

对于 30%的数据，1 <= N <= 20
对于 60%的数据，1 <= N <= 200
对于 100%的数据，1 <= N<= 1500, 0 <= x < N

限制

1s

来源

CWOI新高二专题测试四