题目描述(ID:12367)
标题: 必经之路
标签:
详情:
啊哈星球的城镇之间有道路相连并且而且往往不止一条。但有些路中被林克已经埋伏了重兵。啊哈沃德带着英菲妮特需要从a城到b城,为了减少不必要的麻烦,他们通常会绕行。可啊哈沃德却发现:从a城到b城不管怎么走,总有一些无法避开的必经之路。请问a到b的所有路径中,有几条路是无法避开的?
输入格式:
第一行是n和m,用空格隔开。接下来m行,每行两个整数x和y,用空格隔开,表示x城和y城之间有一条长为1的双向路。第m+2行是q。接下来q行,每行两个整数a和b,用空格隔开,表示一次询问。
输出格式:
对于每次询问,输出一个正整数,表示a城到b城必须经过几条路。
限制: 共10组数据,每组10分。

有3组数据,n ≤ 100 , n ≤ m ≤ 200 , q ≤ 100。
另有2组数据,n ≤ 1000 , n ≤ m ≤ 2000 , 100 < q ≤ 100000。
另有3组数据,1000 < n ≤ 100000 , m = n-1 , 100 < q ≤ 100000。
另有2组数据,1000 < n ≤ 100000 , n ≤ m ≤ 200000 , 100 < q ≤ 100000。

对于全部的数据,1 ≤ x,y,a,b ≤ n;对于任意的道路,两端的城市编号之差不超过10000;
任意两个城镇都有路径相连;同一条道路不会出现两次;道路的起终点不会相同;查询的两个城市不会相同。
样例:

输入

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

输出

0
1

解释

第1次询问,1到4的路径有 1--2--4 ,还有 1--3--4 。没有逃不掉的道路,所以答案是0。
第2次询问,2到5的路径有 2--4--5 ,还有 2--1--3--4--5 。必须走“4--5”这条路,所以答案是1。
登录并解答