#P2017. 分组

分组

Problem Description

kuro在自学的时候,开始沉迷一款叫做maimai的音游。

在音游中,玩家需要按照某种时间点击打音符,根据击打时间和标准击打时间的差距进行评判玩家分数。

在游玩中,有经验的玩家一般会将某些需要击打的音符看成是一组音符,一起处理,以降低难度。

kuro想尝试这种方案。具体的说,一共有nn个音符,每次会给出kk个音符,kuro认定它们应该属于同一组。

两个音符aa,bb当且仅当符合以下两种情况时属于同一组(具体例子请阅读样例和样例解释)

1.a,ba,b在kuro的某一次认定中被认为属于同一组音符

2.a,ca,c因为第一种或此前因该种情况被认为属于同一组音符,b,cb,c也因为第一种或此前因该种情况被认为属于同一组音符

现在给出音符的总数,以及给出qq组kuro认为应该属于同一组的音符,kuro感到很好奇,一共有多少组音符呢?

注意:没有被认为和其他音符属于同一组的音符应该也属于某一组,且该组的成员只有其自己。

Input Format

每个测试点的第一行包含两个整数 nn 和 qq(1≤n≤1051 \leq n \leq 10^5, 0≤q≤1050 \leq q \leq 10^5),分别表示音符的总数和给出的分组数量。

接下来的 qq 行,每行的第一个整数k(0≤k≤105)k (0 \leq k \leq 10^5)表示该组的音符数量,若k不为0,接下来的 kk 个整数为音符的编号ai(0≤i≤k)a_i(0 \leq i \leq k)(1≤ai≤n)(1 \leq a_i \leq n)。

保证每个测试点的所有kk的总和不超过10610^6

注意:可能会出现在前面被认为是同一组的音符再次被认为属于同一组(详情请看样例)

Output Format

输出一个整数,表示最终的音符组数。

Sample

输入 #1

6 5
3 1 2 5
2 4 3
2 1 5
2 6 6
2 1 1

输出 #1

3

样例解释

  • 输入的第二行表示音符 1, 2, 5 属于同一组。
  • 第三行表示音符 3, 4 属于另一组。
  • 第四行此前音符 5 已经与音符 1, 2 在同一组中,实际上没有任何影响
  • 第五,六行并没有进行任何合并操作,实际上没有任何影响
  • 因此最终分为 3 组:{1, 2, 5} , {4, 3} 和 {6}。

输入 #2

6 0

输出 #2

6

样例解释

  • 并没有进行任何合并操作。

输入 #3

6 3
3 1 2 3
2 4 5
3 1 5 2

输出 #3

2

样例解释

  • 输入的第二行表示音符 1, 2, 3 属于同一组。
  • 第三行表示音符 4, 5 属于另一组。
  • 第四行合并了前两行产生的两组。
  • 因此最终分为 2 组:{1, 2, 3, 4, 5} 和 {6}。

Hint

p.s.这道题还有medium version和hard version,期待能在未来让这两个版本问世,敬请关注2025重邮校赛