现代社会,路是必不可少的。
共有 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≤10^5,m≤2∗10^5,q≤10^5
对于全部的数据, 1≤x,y,a,b≤n; ; 对于任意的道路,两端的城市编号之差不超过 10^4 ;
任意两个城镇都有路径相连;同一条道路不会出现两次;道路的起终点不会相同;查询的两个城市不会相同。