추이 폐포

방향 그래프 $G = (V, E)$가 주어진다. $G$의 추이 폐포(transitive closure) 는 원소가 $0$ 또는 $1$인 $|V| \times |V|$ 크기의 행렬 $R$로 나타낼 수 있다. 두 정점 $A$, $B$에 대해 $A$에서 $B$로 가는 경로가 존재하면 $R$의 $A$행 $B$열 값을 $1$로, 존재하지 않으면 $0$으로 채운다.

행렬 $R$ 자체는 매우 커질 수 있으므로, 서로 다른 두 정점 $X \ne Y$에 대해 $X$에서 $Y$로 가는 경로가 존재하는 순서쌍 $(X, Y)$의 개수만 출력한다. 즉, 행렬 $R$에서 행과 열이 서로 다른(행 $\ne$ 열) 칸 중 값이 $1$인 칸의 개수를 구하는 것이다.

경로는 간선을 한 개 이상 지나야 하며, 자기 자신으로 돌아오는 경우($X = Y$)는 세지 않는다.

첫 줄에 테스트 케이스의 개수 $T$ ($T \le 10$)가 주어진다.

각 테스트 케이스의 첫 줄에는 정점의 수 $N$과 간선의 수 $M$이 주어진다 ($2 \le N \le 2{,}500$, $1 \le M \le 10{,}000$). 이어지는 $M$개의 줄에는 각각 두 정수 $A$, $B$ ($1 \le A, B \le N$)가 주어지며, 이는 $A$에서 $B$로 가는 방향 간선이 존재함을 뜻한다. 같은 간선이 두 번 이상 주어지지는 않는다.

각 테스트 케이스마다 $X \ne Y$이면서 $X$에서 $Y$로 가는 경로가 존재하는 순서쌍 $(X, Y)$의 개수를 한 줄에 출력한다.

첫 번째 테스트 케이스의 첫 번째 그래프($N = 3$, 간선 $1 \to 2$와 $2 \to 3$)에서, $G$의 추이 폐포 행렬 $R$은 다음과 같다.

0 1 1
0 0 1
0 0 0

이 행렬에서 행과 열이 서로 다른(행 $\ne$ 열) 칸 중 값이 $1$인 칸은 $3$개이므로 답은 $3$이다.