该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

0x60图论（练习）16：交通实时查询系统

UVA1464 Traffic Real Time Query System

题目描述

一个城市有 $n$ 个路口，$m$ 条无向公路。

你需要回答 $Q$ 组询问。每组询问给出 $S,T$，求从第 $S$ 条路到第 $T$ 条路必须经过的点有几个。

原图不保证连通，但保证每次询问的第 $S$ 条公路和第 $T$ 条公路能相互到达。

输入格式

本题有多组数据。

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

接下来有 $M$ 行，第 $i$ 行（$i$ 从 $1$ 开始）有 $2$ 个整数 $X_i$ 和 $Y_i$，表示第 $i$ 条无向公路连接 $X_i$ 与 $Y_i (X_i\neq Y_i)$。

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

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

输入以 0 0 结束。

输出格式

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

输入输出样例 #1

输入 #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

说明/提示

$0< N\leq 10000$，$0< M\leq 100000$，$0< Q\leq10000$，$0< Xi,Yi\leq N$，$0< S,T≤M$