14 级直升研究生机考

B. 我认识你

单点时限: 2.0 sec

内存限制: 256 MB

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

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

输入格式

第一行有两个整数 $n, m$ $(1 \leq n \leq 40~000, 1 \leq m \leq 40~000)$。分别表示用户数量和好友关系数量。方便起见,用户编号为 $1$ 到 $n$。

接下来 $m$ 行,每行两个整数用空格隔开 $u, v$ $(1 \leq u,v \leq n, u \neq v)$,表示 $u$ 和 $v$ 是好友。数据保证不会出现两对相同的 $u, v$。

接下来一行一个整数 $q$ $(1 \leq q \leq 40~000)$ 表示查询数。

接下来 $q$ 行,每行两个整数 $s, t$ $(1 \leq s,t \leq n, s \neq t)$,表示询问的对象。

小数据规模说明:

  • 对于前 $20\%$ 的数据有 $1 \leq n \leq 10, 1 \leq q \leq 200$。
  • 对于前 $40\%$ 的数据有 $1 \leq n \leq 1~000$。

输出格式

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

样例

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