2258: 最短路上的统计

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:170 Solved:93

Description

一个无向图上,没有自环,所有边的权值均为1,对于一个点对(a,b),我们要把所有a与b之间所有最短路上的点的总个数输出。

Input

第一行n,m,表示n个点,m条边, 接下来m行,每行两个数a,b,表示a,b之间有条边, 再下来一个数p,表示问题的个数, 接下来p行,每行两个数a,b,表示询问a,b

Output

对于每个询问,输出一个数c,表示a,b之间最短路上点的总个数

Sample Input Copy

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

Sample Output Copy

4
3
2

HINT

范围:n< =100,p< =5000

加入题单

算法标签: