3641. [CH #24C]逃不掉的路

【题目描述】

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

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

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

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

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

【输入格式】

第一行是 n 和 m，用空格隔开。

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

第 m+2 行是 q。

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

【输出格式】

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

每个输出占一行。

【样例输入】

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

【样例输出】

0
1

【数据规模与约定】

n≤1e5,m≤2∗1e5,q≤1e5

对于全部的数据，1≤x,y,a,b≤n；对于任意的道路，两端的城市编号之差不超过 1e4；

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