#P10953. 逃不掉的路

逃不掉的路

题目描述

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

共有 nn 个城镇,mm 条道路,任意两个城镇都有路相连,而且往往不止一条。

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

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

他想请你计算一下,aabb 的所有路径中,有几条路是逃不掉的?

输入格式

第一行是 nnmm,用空格隔开。

接下来 mm 行,每行两个整数 xxyy,用空格隔开,表示 xx 城和 yy 城之间有一条长为 11 的双向路。

m+2m+2 行是 qq

接下来 qq 行,每行两个整数 aabb,用空格隔开,表示一次询问。

输出格式

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

每个输出占一行。

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

提示

1n1051\le n \le 10^51m2×1051\le m \le 2\times 10^51q1051\le q \le 10^5
对于全部的数据,1x,y,a,bn1 \le x,y,a,b \le n;对于任意的道路,两端的城市编号之差不超过 10410^4
任意两个城镇都有路径相连;同一条道路不会出现两次;道路的起终点不会相同;查询的两个城市不会相同。