题目描述

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

该城市有 $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

样例解释

道路编号及连接： 1: 1-2
2: 1-3
3: 2-3
4: 3-4
5: 4-5
6: 3-5

询问1：从道路2到道路3
道路2连接1-3，道路3连接2-3。
可以直接走道路2->道路3（共用点3），没有必经的交叉口，输出0。

询问2：从道路2到道路4
道路2连接1-3，道路4连接3-4。
必经的交叉口是3，输出1。

数据范围

• $0 < N \leq 10000$
• $0 < M \leq 100000$
• $0 < Q \leq 10000$
• $0 < X, Y \leq N$
• $0 < S, T \leq M$

时空限制

• 时间限制：2 秒
• 空间限制：64 MB