1215: 共现的数

Memory Limit：128 MB Time Limit：2.000 S Judge Style：Text Compare Creator：
Submit：9 Solved：5

Description

给出n个包含整数的集合，当两个整数至少同时出现在一个集合中时我们认为两个整数存在共现关系.

给定两个整数x、y，我们需要计算有多少个不同的整数同时和x、y存在共现关系.

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

包含不超过10组测试数据.

每组测试数据的第一行包含一个整数n，表示一共有n个集合.

接下来n行依次描述的这n个集合，每行第一个整数mi表示集合中整数的数量，接下来mi个正整数表示该集合中的各个元素.

接下来一行包含一个整数q，表示接下来有q次询问.

每个询问占一行，包含两个整数x、y.

数据保证x和y均至少在一个集合中出现过.（如果不满足这个条件，请输出0）

  • 1 ≤n≤ 50
  • 1 ≤mi≤ 500
  • 1 ≤q≤ 500
  • 集合中的整数不大于10e4

Output

对于每次询问，输出有多少个不为x或y且不同的整数同时和x、y存在共现关系.


Sample Input Copy 

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

Sample Output Copy 

2
3
3
3
1

HINT

样例说明：

同时和1、2共现的整数为：3、5
同时和1、3共现的整数为：2、4、5
同时和2、4共现的整数为：1、3、5
同时和1、5共现的整数为：2、3、4
同时和5、6共现的整数为：2


提示：本题数据十分的大，如果正常做法时间复杂度是O(n)，所以用二进制进行优化

Source/Category