Transitive Closure#3330
In almost all ICPC trainings, one of the basic items to be taught (or even better, assumed) is how to compute the transitive closure of a directed graph. Since this concept is so elementary, there is a professor that suggests to solve this problem using Warshall's algorithm. As one of the bonus tasks of this ICPC, we would like to examine whether the participants have indeed mastered this technique.
Given a directed graph G = < V, E > with N = |V| vertices (2 \leq N \leq 2500) and M = |E| edges (1 \leq M \leq 10000), its transitive closure is the binary relation on such that two vertices, and , are related in if there is a directed path from to , where a directed path is a sequence of edges of the graph C_0C_1, C_1C_2, ..., C_{K-1}C_K such that A = C_0 and B = C_K. Your task is to compute .
Because might be very large, we've decided to simplify the output. Calculate the number of ordered pairs of (, ) where is not equal to such that there is a path from vertex to vertex in graph .
The first line of input contains an integer (T \leq 10), denoting the number of testcases. The following lines describe each test case of the following format.
The first line of a testcase consists of two integers and . Each of the following lines contains integers, and , denoting that there is a directed edge from to . The vertices are numbered from to , and there will be no repeated edges within a description of a graph.
For each case, output an integer denoting the number of ordered pairs of (, ) where is not equal to such that there is a path from vertex to vertex .
Esempio 1