odd doctor 已更新

CRB and Roads

Time Limit
6s
Memory Limit
131072KB
Judge Program
Standard
Ratio(Solve/Submit)
100.00%(1/1)
Description:

There are N cities in Codeland.
The President of Codeland has a plan to construct one-way roads between them.
His plan is to construct M roads.
But CRB recognized that in this plan there are many redundant roads.
So he decided to report better plan without any redundant roads to President.
Help him!
The road (uv) is redundant if and only if there exists a route from u to v without using it.

Input:

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers N and M denoting the number of cities and the number of roads in the President’s plan.
Then M lines follow, each containing two integers u and v representing a one-way road from u to v.
1 ≤ T ≤ 20
1 ≤ N ≤ 2 * 104
1 ≤ M ≤ 105
1 ≤ uv ≤ N
The given graph is acyclic, and there are neither multiple edges nor self loops.

Output:

For each test case, output total number of redundant roads.

Sample Input:
1
5 7
1 2
1 3
1 4
1 5
2 4
2 5
3 4
Sample Output:
2
Source:

2015 Multi-University Training Contest 10


Submit