Transitive Closure

You are given a directed graph $G = (V, E)$. The transitive closure of $G$ can be represented as a $|V| \times |V|$ matrix $R$ whose entries are $0$ or $1$: for two vertices $A$ and $B$, the entry in row $A$, column $B$ is $1$ if there is a path from $A$ to $B$, and $0$ otherwise.

Because the matrix $R$ itself can be very large, output only the number of ordered pairs $(X, Y)$ with $X \ne Y$ such that a path from $X$ to $Y$ exists. In other words, count the cells of $R$ that hold $1$ and lie off the diagonal (row $\ne$ column).

A path must use at least one edge, and a vertex returning to itself ($X = Y$) is never counted.

The first line contains the number of test cases $T$ ($T \le 10$).

Each test case begins with a line containing the number of vertices $N$ and the number of edges $M$ ($2 \le N \le 2{,}500$, $1 \le M \le 10{,}000$). The next $M$ lines each contain two integers $A$ and $B$ ($1 \le A, B \le N$), meaning there is a directed edge from $A$ to $B$. No edge is given more than once.

For each test case, print on a single line the number of ordered pairs $(X, Y)$ with $X \ne Y$ such that a path from $X$ to $Y$ exists.

For the first graph of the first test case ($N = 3$, edges $1 \to 2$ and $2 \to 3$), the transitive-closure matrix $R$ of $G$ is:

0 1 1
0 0 1
0 0 0

Exactly $3$ off-diagonal cells (row $\ne$ column) hold $1$, so the answer is $3$.