3337. 我认识你

单点时限: 2.0 sec

内存限制: 256 MB

人与人之间的关系错综复杂,常常会出现一个叫作共同好友的东西。所以,贴心的 QQ 就提供了这样一个功能,可以显示你与某人(不一定是好友)有多少个共同好友。但是,当用户量逐渐增大,好友关系网不断复杂化,共同好友计算的效率就变得十分重要了。

你刚刚和腾讯公司签约,获得了共同好友计算的开发资格。

输入格式

第一行有两个整数 。分别表示用户数量和好友关系数量。方便起见,用户编号为

接下来 行,每行两个整数用空格隔开 ,表示 是好友。数据保证不会出现两对相同的

接下来一行一个整数 表示查询数。

接下来 行,每行两个整数 ,表示询问的对象。

小数据规模说明:

  • 对于前 的数据有
  • 对于前 的数据有

输出格式

对于每组询问,输出这两个人有多少个共同好友。

样例

Input
3 3
1 2
1 3
3 2
2
1 3
3 2
Output
1
1
Input
4 4
1 2
1 4
2 3
3 4
3
1 3
1 4
2 4
Output
2
0
2
Input
3 2
1 2
1 3
2
2 3
2 3
Output
1
1

94 人解决,202 人已尝试。

129 份提交通过,共有 946 份提交。

5.0 EMB 奖励。

创建: 2 年,2 月前.

修改: 2 年,1 月前.

最后提交: 1 月,2 周前.

来源: 2017 直升研究生机试

题目标签