SP22554 PRJAN15G - Kingdom
题目描述
Shin 想成为「天界大将军」，这是他的梦想。但这个目标并不简单，实现它需要出众的战斗能力和高超的军事策略。
Shin接到了总部的新任务。敌人正在策划攻击秦国，他必须不惜一切手段阻止敌人。秦国的城市和道路可以看作是一个连通图，其中 $N$ 个节点代表不同的城市，编号从 $1$ 到 $N$，连接城市的道路则是边。
虽然敌人已经潜入了秦国，但他们的确切位置尚不清楚，然而很快敌人内部的间谍会通知Shin他们的位置。同时，敌人计划攻击秦军的总部。总部的具体位置对Shin来说也是未知的，但秦国政府会及时告知他。
虽然Shin暂时不知道敌人和总部的位置，但不久之后他就会知道。当信息到手后，他将率军出击并阻挡敌人。假设敌人的位置是节点 $E$，总部的位置是节点 $H$。
Shin 有一个限制：他只能在道路上迎战敌人，为了保护平民，不允许在城内展开战斗。Shin 必须小心挑选作战的道路。在从 $E$ 到 $H$ 的多条可能路径中，Shin 必须找一条他可以守卫的道路。这样一来，敌人无法绕过Shin而攻击总部。那些关键的道路就是「命运之路」。
因为目前还不知道 $E$ 和 $H$ 的实际位置，Shin有些无聊，决定通过假设一些 $\{E, H\}$ 的组合来训练他的战术技能，并计算出「命运之路」的数量。
现在，Shin 希望你帮助他完成这项计算。给定秦国的交通图，Shin会给出 $Q$ 个查询，每个查询指定一个 $\{E, H\}$ 的组合。请告诉 Shin，有多少条「命运之路」。
输入格式
第一行包含一个整数 $T$ 表示测试用例的数量 ($T \leq 5$)。
对于每个测试用例，第一行包含两个整数 $N$ 和 $R$，分别表示节点数量和道路数量 ($2 \leq N \leq 100000, 1 \leq R \leq 200000$)。接下来 $R$ 行，每行包含一对整数 $U, V$，表示节点 $U$ 和 $V$ 之间有一条道路。接下来是一行整数 $Q$ 表示查询的数量 ($1 \leq Q \leq 100000$)。之后的 $Q$ 行，每行包含一对整数，表示一个查询的 $E$ 和 $H$。
输入保证图是连通的，没有自环或重复边。
输出格式
对于每个测试用例，首先输出一行「Case X:」，其中 $X$ 是测试用例的编号。接着，对于每个查询输出一行，包含一个整数，表示相应查询的「命运之路」数量。
**样例输入**
```
3
3 2
1 2
2 3
2
1 2
1 3
4 4
1 2
1 3
2 4
3 4
1
1 4
5 5
1 2
2 3
3 1
2 4
3 5
1
1 4
```
**样例输出**
```
Case 1:
1
2
Case 2:
0
Case 3:
1
```
**说明**
在第一个测试用例中，查询 1 的结果是 1，因为 Shin 应该守卫的唯一道路是节点 1 和 2 之间的道路；查询 2 可以选择守卫 1->2 或 2->3 中的任意一条。在第二个测试用例中，查询 1 的结果是 0，因为没有「命运之路」。在第三个测试用例中，查询 1 的唯一选择是 2->4。
**本翻译由 AI 自动生成**