CF1616G.Just Add an Edge

You are given a directed acyclic graph with $n$ vertices and $m$ edges. For all edges $a \to b$ in the graph, $a \lt b$ holds.

You need to find the number of pairs of vertices $x$, $y$, such that $x \gt y$ and after adding the edge $x \to y$ to the graph, it has a Hamiltonian path.

给你一个包含 $n$ 个顶点和 $m$ 条边的有向无环图（DAG）。对于图中的所有边 $a \to b$，均满足 $a \lt b$。

你需要找出满足以下条件的顶点对 $x, y$ 的数量：$x \gt y$，且在图中添加边 $x \to y$ 后，该图存在哈密顿路径。

The first line of input contains one integer $t$ ($1 \leq t \leq 5$): the number of test cases.

The next lines contains the descriptions of the test cases.

In the first line you are given two integers $n$ and $m$ ($1 \leq n \leq 150\,000$, $0 \leq m \leq \min(150\,000, \frac{n(n-1)}{2})$): the number of vertices and edges in the graph.

Each of the next $m$ lines contains two integers $a$, $b$ ($1 \leq a \lt b \leq n$), specifying an edge $a \to b$ in the graph. No edge $a \to b$ appears more than once.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 5$）：测试用例的数量。

接下来的若干行包含各测试用例的描述。

第一行给出两个整数 $n$ 和 $m$（$1 \leq n \leq 150\,000$，$0 \leq m \leq \min(150\,000, \frac{n(n-1)}{2})$）：图中顶点和边的数量。

接下来的 $m$ 行每行包含两个整数 $a$、$b$（$1 \leq a \lt b \leq n$），表示图中的一条有向边 $a \to b$。任意边 $a \to b$ 不会重复出现。

For each test case, print one integer: the number of pairs of vertices $x$, $y$, $x \gt y$, such that after adding the edge $x \to y$ to the graph, it has a Hamiltonian path.

对于每个测试用例，输出一个整数：满足条件的顶点对 $x$、$y$（其中 $x \gt y$）的个数，使得在图中添加有向边 $x \to y$ 后，该图存在哈密顿路径。

In the first example, any edge $x \to y$ such that $x \gt y$ is valid, because there already is a path $1 \to 2 \to 3$.

In the second example only the edge $4 \to 1$ is valid. There is a path $3 \to 4 \to 1 \to 2$ if this edge is added.

In the third example you can add edges $2 \to 1$, $3 \to 1$, $4 \to 1$, $4 \to 2$.

在第一个例子中，任意满足 $x \gt y$ 的边 $x \to y$ 均合法，因为已存在路径 $1 \to 2 \to 3$。

在第二个例子中，仅有边 $4 \to 1$ 合法。若添加该边，则存在路径 $3 \to 4 \to 1 \to 2$。

在第三个例子中，你可以添加边 $2 \to 1$、$3 \to 1$、$4 \to 1$、$4 \to 2$。