时间限制： 4.0 秒

空间限制： 512 MB

题目描述

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

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

输入格式

从标准输入读入数据。

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

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

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

接下来 $q$ 行，每行两个整数 $s,t$，表示询问的对象。

小数据规模说明：

输出格式

输出到标准输出。

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

3 3
1 2
1 3
3 2
2
1 3
3 2

1
1

4 4
1 2
1 4
2 3
3 4
3
1 3
1 4
2 4

2
0
2

3 2
1 2
1 3
2
2 3
2 3

1
1

子任务

对于所有数据，有：

• $1\le n,m,q\le 2\times 10^5$
• $1\le u,v,s,t\le n,u\ne v,s\ne t$

本题无数据梯度，需要通过全部数据获得所有分数。