题目描述

你是一座城市的最高指挥官，你的城市道路成树形，结点就是路口，共 \(n\) 个，边就是路口间的道路。

外星文明正准备攻打你的城市，他们准备将士兵随机传送到你所在城市的道路上。为了能够监控所有的道路，你决定安排士兵驻守在路口上，路口上的士兵可以监控到所有与其相连的道路。为了减少开支，你决定驻守最少的路口，以实现能够监控所有道路的目的。

格式

输入格式

第一行一个数字 \(n（1≤n≤1500）\)；

以下 \(N\) 行，每行描述一个点 \(u\) 的所有子结点，第一个数是 \(u\)，第二个数在括号内是子结点个数，后跟所有子结点编号。参考样例输入。

输出格式

一个数表示你最少需要驻守的路口数。

样例1

样例输入1

4
1:(1)2
2:(2)3 4
3:(0)
4:(0)

样例输出1

1

限制

时间：\(1s\) 空间：\(256M\)

对于 \(100\%\) 的数据：\(1≤n≤1500\)；

来源

地址：\(zloj,J2020\)域
作者：\(jiliang2509\)
模拟赛\(T3\)