题目描述

某城市的交通堵塞问题非常严重，为解决这一问题，该城市建立了实时查询系统来检测所有交通情况。

该城市有$N$个交叉口，$M$ 条道路，每条道路连接两个交叉口，且都是双向的。

实时查询系统的一个重要任务就是帮助司机找到从指定道路行驶到另一条指定道路必经的交叉口有多少个。

输入格式

输入包含多组测试数据。

每组数据第一行包含两个整数 $N$和$M$。

接下来 $M$行，每行包含两个不同的整数 $X$和 $Y$，表示交叉口 $X$和 $Y$ 之间存在一条道路，第 i 行的道路编号为 $i$。

接下来一行，包含整数 $Q$，表示查询系统的询问次数。

接下来 $Q$行，每行包含两个整数 $S$和 $T$，表示从道路 $S$ 行驶到道路$T$，输入保证至少有一条道路可以连通$S$ 和$T$。

当输入一行为 0 0 时，表示输入终止。

输出格式

每次询问输出一个整数，表示必须经过的交叉口的个数。

每个结果占一行。

样例

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

0
1

数据范围

$0<N≤10000, 0<M≤100000,0<Q≤10000,0<X,Y≤N,0<S,T≤M$

来源

• HDOJ3686
• 算法竞赛进阶指南