CF1616G Just Add an Edge

给定一个有 $n$ 个顶点和 $m$ 条边的有向无环图。对于图中的所有边 $a \to b$，都有 $a < b$。 你需要找出有多少对顶点 $x$、$y$，满足 $x > y$，并且在图中添加一条边 $x \to y$ 后，图中存在一条哈密顿路径。

输入的第一行包含一个整数 $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 < b \leq n$），表示一条从 $a$ 到 $b$ 的有向边。每条边只出现一次。

对于每个测试用例，输出一个整数，表示有多少对顶点 $x$、$y$，满足 $x > y$，并且在添加边 $x \to y$ 后，图中存在一条哈密顿路径。

在第一个样例中，任意一条 $x \to y$ 且 $x > 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$。 由 ChatGPT 4.1 翻译