电子眼问题

Time Limit: 3000 ms Memory Limit: 65536 KiB

Problem Description

Sicily市是一个环境优美,气候宜人的小城市。因为城市的交通并不繁忙,市内的道路网很稀疏。准确地说,Sicily市有N条马路和N个路口,每条马路连接两个路口,每两个路口之间最多只有一条马路。作为一个交通网络,显然每两个路口之间都是可达的。为了更好地管理Sicily市的交通,市长决定在一些路口加装电子眼,用来随时监视路面情况。这些装在路口的电子眼能够监视所有的马路。市长已经把所有的路口都编上了1到n的号码。

给你Sicily市的地图,你能帮个忙吗?

Input

输入的第1行包括一个数字N(1<=N<=100000),表示Sicily市的路口数(马路数)。以下N行,第i+1行的第1个数字Ki表示有Ki条马路与路口i相连,后面紧接着Ki 个数字,表示与路口i直接连接的路口。

Output

对于每组输入的测试数据,输出一个需要安装电子眼的最少的路口数。

Sample Input

3
2 2 3
2 1 3
2 1 2

Sample Output

2

Hint

求有N个点N条边的连通图的最小覆盖集,要求做到O(n)。

Source