题目描述

现代社会，路是必不可少的。

共有$\red {n}$个城镇，$\red {m}$条道路，任意两个城镇都有路相连，而且往往不止一条。

但有些路年久失修，走着很不爽。

按理说条条大路通罗马，大不了绕行其他路呗——可小撸却发现：从$\red {a}$城到$\red {b}$城不管怎么走，总有一些逃不掉的必经之路。

他想请你计算一下，$\red {a}$到$\red {b}$的所有路径中，有几条路是逃不掉的？

输入格式

第一行是$\red {n}$和$\red {m}$，用空格隔开。

接下来$\red {m}$行，每行两个整数$\red {x}$和$\red {y}$，用空格隔开，表示$\red {x}$城和$\red {y}$城之间有一条长为$\red {1}$的双向路。

第$\red {m+2}$行是$\red {q}$。

接下来$\red {q}$行，每行两个整数$\red {a}$和$\red {b}$，用空格隔开，表示一次询问。

输出格式

对于每次询问，输出一个正整数，表示$\red {a}$城到$\red {b}$城必须经过几条路。

每个输出占一行。

样例

输入样例

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

输出样例

0
1

提示

$\red {n≤10 ^5 ,m≤2\times 10 ^5 ,q≤10^5}$

对于全部的数据，$\red {1≤x,y,a,b≤n}$；对于任意的道路，两端的城市编号之差不超过$\red {10^4}$；

任意两个城镇都有路径相连；同一条道路不会出现两次；道路的起终点不会相同;查询的两个城市不会相同