#P14578. [Bulgarian 2025]mushrooms

[Bulgarian 2025]mushrooms

题目描述

小红帽刚刚从附近的小树林里满载而归,完成了一次非常成功的采蘑菇之旅。她一共采到了 NN 个蘑菇,编号为 11 到 NN。在采蘑菇的过程中,她使用了 MM 个编织篮子,编号为 11 到 MM。对于每个篮子 ii,她知道曾经有哪些蘑菇放进过这个篮子。

现在她担心,有些蘑菇可能是有毒的红色毒蝇伞。更糟的是,它们可能在曾经待过的篮子里留下毒素,而这些毒素又可能毒害其他曾在同一个篮子里的蘑菇。

为了调查清楚,小红帽需要回答 QQ 个问题。每个问题给出两个蘑菇 AjA_j 和 BjB_j,她想知道:

  • 这两个蘑菇共同出现过在哪些篮子里;
  • 但为了更快,她不需要完整列表,只需要这些公共篮子编号之和。

请你编写程序,回答这些询问。

输入格式

第一行输入两个整数 N,MN, M。

接下来 MM 行描述每个篮子。第 ii 行先输入一个整数 KiK_i,表示第 ii 个篮子里曾经放过多少个蘑菇;随后输入这 KiK_i 个蘑菇的编号。

接下来输入一个整数 QQ。

随后 QQ 行,每行输入两个不同的整数 Aj,BjA_j, B_j,表示一次询问。

输出格式

对于每个询问,输出一行一个整数,表示这两个蘑菇共同出现过的所有篮子的编号之和。

约束条件

记

S=∑iKiS = \sum_i K_i

则有:

  • 1≤N≤1051 \le N \le 10^5
  • 1≤S≤1051 \le S \le 10^5
  • 1≤Q≤1051 \le Q \le 10^5
  • 2≤Ki≤N2 \le K_i \le N
  • 1≤M≤S/21 \le M \le S/2
  • 1≤Aj,Bj≤N1 \le A_j, B_j \le N
  • Aj≠BjA_j \ne B_j

子任务

子任务 分值 限制
1 14 N,S,Q≤1000N,S,Q \le 1000
2 12 N≤100N \le 100
3 7 Ki≤100K_i \le 100
4 M≤100M \le 100
5 12 每个蘑菇至多出现在 100100 个篮子中
6 48 无额外限制

对于某个子任务,只有当该子任务以及它所包含的所有测试点全部通过时,才能获得该子任务分数。

样例

输入

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

输出

1
3
0
5

样例解释

  1. 蘑菇 11 和 22 都曾在篮子 11 中出现过,因此答案为 11。
  2. 蘑菇 22 和 55 都曾在篮子 33 中出现过,因此答案为 33。
  3. 蘑菇 33 和 66 没有共同出现过的篮子,因此答案为 00。
  4. 蘑菇 55 和 66 都曾在篮子 22 和 33 中出现过,因此答案为 2+3=52+3=5。