题面翻译

一个城市有$n$个路口，$m$条无向公路。求从第$S$条路到第$T$条路必须经过的点有几个。

输入格式

第一行有两个整数 $N$ 和 $M$，表示路口和道路的数量。

接下来有$M$行，第$i$ 行( $i$ 从1开始)有2个整数 $X_i$ 和 $Y_i$ ，表示 $road_i$ 连接$X_i$与$Y_i$ $(X_i≠Y_i)$。

下面一行有一个整数$Q$，表示询问的数量。

接下来$Q$ 行，每一行包含两个整数$S$ 和 $T$ $(S≠ T)$。

输入以“0 0”结束。

请注意:$0< N≤10000,0< M≤100000,0< Q≤10000,0< Xi,Yi≤N, 0< S,T≤M$

输出格式

对于每个询问，输出一行表示答案

输入输出样例

输入 #1

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

输出 #1

0
1

题目描述

PDF