#P0832. 聚合离散

聚合离散

题目描述

勾心斗角

某星光高中近期发现许多学生之间建立了一个又一个的小团体,现在老师对这个问题开始着手解决了。

班级中有nn名同学,每位同学都有一个仰慕的同学,每位同学仰慕的同学互不相同,同学可以仰慕自己,且:

  • 传递性:如果AA仰慕BB,BB仰慕CC,那么AA也仰慕CC。
  • 非对称性:如果AA仰慕BB,BB不一定仰慕AA。

根据仰慕关系,学生之间形成以下类型的团体:

  • 互慕团体:一个人数至少为22的学生集合 SS,其中对于任意两名不同的学生 a,b∈Sa, b \in S,aa 仰慕 bb 且 bb 仰慕 aa(即相互仰慕);或者SS中只有一名学生,且他自己仰慕自己。

  • 单慕团体:一个人数至少为22的学生集合 SS,其中对于任意两名不同的学生 a,b∈Sa, b \in S,aa 仰慕 bb 或 bb 仰慕 aa(即有单向仰慕关系),但并非所有人都相互仰慕;或者 SS 中只有一名学生,且他不仰慕自己。

  • 孤立团体:只有一名学生的单慕团体。

  • 非孤立单慕团体:不是孤立团体的单慕团体。

老师为了防止小团体影响学生们的成绩,开始了拆散计划:老师将点名约谈kk位同学,如果同学AA被约谈,AA对所有曾经“仰慕”的同学都将变为“讨厌”关系(AA仰慕BB →\rightarrow AA讨厌BB)。进而,BB将被所在团体孤立出去,并不再仰慕任何人(包括自己),原先包含BB的”互慕团体“中的同学将不再相互仰慕而变成“单慕团体”,原先包含BB的“单慕团体”也可能被分裂成多个“单慕团体”,同时BB自己一个人变成一个“孤立团体”。

经过约谈,班级里的团体被拆的七零八散,同学们察觉到了老师的意图,团结了起来。

同学们相互沟通,所有“非孤立单慕团体”将两两配对,每两个”非孤立单慕团体“将相互仰慕合并成一个新的”互慕团体“。如果有落单的”非孤立单慕团体“,那他将变成孤立收容所,将所有的”孤立团体“纳入其中,组建成一个新的”互慕团体“。

如果没有孤立收容所,每个”孤立团体“都将自立自爱,成为一个只有自己一个人的”互慕团体“。

请问最后,班级中会剩多少个互慕团体呢?

输入格式

本题包含多组测试数据。

第一行为一个整数T(1≤T≤2×105)T(1 \le T \le 2 \times 10^5),表示测试数据组数。

对于每组测试数据,第一行为一个整数n(1≤n≤5×105)n(1 \le n \le 5 \times 10^5),班级中的人数。

第二行包含nn个整数a1,a2,...,an(1≤ai≤n)a_1, a_2, ... , a_n(1 \le a_i \le n),其中aia_i表示同学ii仰慕的同学编号。保证如果i≠j(1≤i,j≤n)i \not = j(1 \le i, j \le n),则ai≠aja_i \not= a_j。

第三行为一个整数k(1≤k≤n)k(1 \le k \le n),老师带走约谈的同学数。

第四行包含kk个整数b1,b2,...,bk(1≤bi≤n)b_1, b_2, ..., b_k(1 \le b_i \le n),被老师带走约谈的kk位同学的编号。保证如果i≠j(1≤i,j≤k)i \not = j(1 \le i, j \le k),则bi≠bjb_i \not= b_j。

对于所有测试数据,保证∑n≤5×105\sum n \le 5 \times 10^5。

输出格式

对于每组测试数据,输出一行一个整数,表示班级中最后剩下的互慕团体数。

样例

3
7
2 1 5 3 4 7 6
2
2 4
10
5 3 9 8 7 6 1 10 2 4
4
3 1 5 8
9
2 3 4 5 6 7 8 9 1
3
1 3 5
2
7
1

提示

对于第一组测试数据,老师约谈后的团体情况为:

  • 互慕团体:{6,7}\{6, 7\}
  • 非孤立单慕团体:{3,5}\{3, 5\}
  • 孤立团体:{1},{2},{4}\{1\}, \{2\}, \{4\}

原来有 11个互慕团体 ,落单的非孤立单慕团体变为孤立收容所,和所有的孤立团体共同组成 11个互慕团体。

对于第二组测试数据,老师约谈后的团体情况为:

  • 互慕团体:{6}\{6\}
  • 非孤立单慕团体:{9,2},{10,4}\{9, 2\},\{10, 4\}
  • 孤立团体:{1},{3},{5},{7},{8}\{1\}, \{3\}, \{5\}, \{7\}, \{8\}

原来有 11个互慕团体,两个非孤立单慕团体组成 11个互慕团体后,没有落单的非孤立单慕团体。55个孤立团体变成 55个互慕团体。