交通实时查询系统

【题目描述】

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

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

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

【输入格式】

输入包含多组测试数据。

每组数据第一行包含两个整数 $n$ 和 $m$。

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

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

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

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

【输出格式】

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

每个结果占一行。

【样例输入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

【输入输出样例2】

输入输出样例2

【数据规模与约定】

对于 $10 \%$ 的数据，$1 \leq n,m,q \leq 12$;

对于 $60 \%$ 的数据，$1 \leq n \leq 1000,1 \leq m \leq 1100,1 \leq q \leq 500$;

对于 $100 \%$ 的数据，$1 \leq n \leq 10000,1 \leq m \leq 100000,$

$1 \leq q \leq 10000,1 \leq x,y \leq n,1 \leq s,t \leq m$，数据组数不超过 $5$。

【来源】

$UVA1464$ $Traffic$ $Real$ $Time$ $Query$ $System$