当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6604:Blow up the city

题目描述
Country A and B are at war. Country A needs to organize transport teams to deliver supplies toward some command center cities.

In order to ensure the delivery works efficiently, all the roads in country A work only one direction. Therefore, map of country A can be regarded as DAG( Directed Acyclic Graph ). Command center cities only received supplies and not send out supplies.

Intelligence agency of country B is credibly informed that there will be two cities carrying out a critical transporting task in country A.

As long as **any** one of the two cities can not reach a command center city, the mission fails and country B will hold an enormous advantage. Therefore, country B plans to destroy one of the $n$ cities in country A and all the roads directly connected. (If a city carrying out the task is also a command center city, it is possible to destroy the city to make the mission fail)

Now country B has made $q$ hypotheses about the two cities carrying out the critical task.
Calculate the number of plan that makes the mission of country A fail.
输入解释
The first line contains a integer $T$ $(1 \leq T \leq 10)$, denoting the number of test cases.

In each test case, the first line are two integers $n, m$, denoting the number of cities and roads$(1\leq n\leq 100,000, 1\leq m\leq 200,000)$.
Then $m$ lines follow, each with two integers $u$ and $v$, which means there is a directed road from city $u$ to $v$ $(1\leq u, v\leq n, u \neq v)$.

The next line is a integer q, denoting the number of queries $(1\leq q\leq 100,000)$
And then $q$ lines follow, each with two integers $a$ and $b$, which means the two cities carrying out the critical task are $a$ and $b$ $(1\leq a, b\leq n, a \neq b)$.

A city is a command center if and only if there is no road from it (its out degree is zero).
输出解释
For each query output a line with one integer, means the number of plan that makes the mission of country A fail.
输入样例
2
8 8
1 2
3 4
3 5
4 6
4 7
5 7
6 8
7 8
2
1 3
6 7
3 2
3 1
3 2
2
1 2
3 1
输出样例
4
3
2
2
来自杭电HDUOJ的附加信息
Recommend chendu

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6604

最后修改于 2020-10-25T23:32:44+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/5000MS(Java/Others) 131072/131072K(Java/Others)