3864: Blow up the city
内存限制：128 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
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.
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≤T≤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≤n≤100,000,1≤m≤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≤u,v≤n,u≠v).
The next line is a integer q, denoting the number of queries (1≤q≤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≤a,b≤n,a≠b).
A city is a command center if and only if there is no road from it (its out degree is zero).
In each test case, the first line are two integers n,m, denoting the number of cities and roads(1≤n≤100,000,1≤m≤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≤u,v≤n,u≠v).
The next line is a integer q, denoting the number of queries (1≤q≤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≤a,b≤n,a≠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