题目描述

Farmer John is throwing a party and wants to invite some of his cows to show them how much he cares about his herd. However, he also wants to invite the smallest possible number of cows, remembering all too well the disaster that resulted the last time he invited too many cows to a party.

Among FJ's cows, there are certain groups of friends that are hard to separate. For any such group (say, of size k), if FJ invites at least k-1 of the cows in the group to the party, then he must invite the final cow as well, thereby including the entire group. Groups can be of any size and may even overlap with each-other, although no two groups contain exactly the same set of members. The sum of all group sizes is at most 250,000.

Given the groups among FJ's cows, please determine the minimum number of cows FJ can invite to his party, if he decides that he must definitely start by inviting cow #1 (his cows are conveniently numbered 1..N, with N at most 1,000,000).

输入格式

* Line 1: Two space-separated integers: N (the number of cows), and G (the number of groups).

* Lines 2..1+G: Each line describes a group of cows. It starts with an integer giving the size S of the group, followed by the S cows in the group (each an integer in the range 1..N).

输出格式

* Line 1: The minimum number of cows FJ can invite to his party.

题目大意

农夫约翰要举办一个聚会，他要邀请一些奶牛来参加。在约翰的奶牛朋友圈中，有一些奶牛是好基友，对于每一个奶牛朋友圈，没有一个完全与之相同的，假设这个奶牛朋友圈有 $k$ 头奶牛，如果约翰已经邀请了 $k-1$ 头，那么剩下的那头牛也得邀请。约翰想让你告诉他，他最少需要邀请多少头奶牛？我们假设 $1$ 号奶牛已经被邀请了。

【输入格式】

第一行 $N$ 和 $G$ 表示共有 $N$ 头奶牛和 $G$ 个朋友圈。

接下来 $G$ 行，每行开头输入一个整数 $k$，表示朋友圈里有 $k$ 头牛，接着输入 $k$ 个整数，表示朋友圈里的牛。

【输出格式】

一行，一个整数，表示约翰最少需要邀请的牛的头数。

【数据范围】

$1 \leq N\leq1000000$。

设所有的奶牛朋友圈的大小之和为 $M$，则 $1 \leq M\leq250000$。

10 4 
2 1 3 
2 3 4 
6 1 2 3 4 6 7 
4 4 3 2 1 

4 

提示

There are 10 cows and 4 groups. The first group contains cows 1 and 3, and so on.

In addition to cow #1, FJ must invite cow #3 (due to the first group constraint), cow #4 (due to the second group constraint), and also cow #2 (due to the final group constraint).