CF2187C Jerry and Tom

Jerry 和 Tom 正在一个有向图 $G$ 上玩游戏。图 $G$ 有 $n$ 个顶点，编号从 $1$ 到 $n$。对于每个顶点 $1 \le u < n$，都有一条从 $u$ 指向 $u+1$ 的有向边。此外，还有 $m$ 条额外的有向边。第 $i$ 条额外的边从 $u_i$ 指向 $v_i$，其中 $1 \le u_i < v_i \le n$。 这个图 $G$ 有如下特殊性质：不存在两条有向边 $(u_i\to v_i)$ 和 $(u_j\to v_j)$ 满足 $u_i < u_j < v_i < v_j$。 游戏开始时，Jerry 和 Tom 分别站在顶点 $x$ 和 $y$ 上，其中 $x \ne y$。游戏按回合进行，每回合按照以下规则进行操作，Jerry 先行动，Tom 后行动： - Jerry 必须选择一条从当前位置出发的有向边并沿该边移动到终点。如果当前顶点没有出边，他就停在原地。 - Tom 可以选择一条从当前位置出发的有向边并沿该边移动到终点，或者选择不移动，停在原地。 每当回合结束后，如果 Jerry 和 Tom 站在同一个顶点（包括顶点 $n$），游戏立即结束，Tom 获胜。否则，如果 Jerry 一开始就在顶点 $n$，或者在回合结束后到达顶点 $n$，Jerry 获胜。 注意，如果一个回合后，两人都在顶点 $n$，则 Tom 获胜。 在整个游戏过程中，两名玩家都能知道对方的位置。 可以证明，这个游戏必定在有限的回合数内结束。 对于每一对整数 $1 \le x,y \le n$，$x \ne y$，定义 $f(x,y)$ 如下： - Jerry 和 Tom 进行游戏，Jerry 从顶点 $x$ 出发，Tom 从顶点 $y$ 出发。Tom 目标是获胜，并且尽量减少他实际移动的次数（即更换顶点的回合数；原地不动不计为移动）。假设两人都采取最优策略，则若 Tom 无法获胜，则 $f(x,y)=0$；否则，$f(x,y)$ 为 Tom 至少需要几次移动才能确保获胜。如果在最优对弈下 Tom 能获胜，Jerry 会尽量让 Tom 移动次数最多。 计算 $$ \sum\limits_{1 \le x,y \le n,\, x \ne y}f(x,y). $$

每个测试点包含多个测试用例。第一行输入整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$0 \le m \le n-2$），表示图的顶点数和额外有向边的数量。 接下来 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i + 1 < v_i$），表示一条额外的有向边。保证任意有序点对 $(u,v)$，至多有一条从 $u$ 到 $v$ 的边。并且保证不存在两条有向边 $(u_i\to v_i)$ 和 $(u_j\to v_j)$ 满足 $u_i < u_j < v_i < v_j$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示所求和的值。

在第一个测试用例中： - $x=1$，$y=2$：Jerry 被迫在第一回合移动到 $2$。Tom 可以在 $2$ 等待。当第一回合结束时，Jerry 和 Tom 都在 $2$，因此有 $f(1,2)=0$，Tom 无需移动即可获胜。 - $x=2$，$y=1$：Jerry 一开始就在 $n=2$，Tom 无法获胜。因此 $f(2,1)=0$。 在第三个测试用例中，Tom 能获胜的 $(x,y)$ 情况如下： - 若 $x=1,2,3$ 且 $y=4$。无论 Jerry 怎么走，Tom 均可一直待在 $4$ 等 Jerry 到来，Tom 不需移动即可获胜。因此 $f(1,4)=f(2,4)=f(3,4)=0$。 - 若 $x=1,2$ 且 $y=3$，无论 Jerry 第一回合怎么走，Tom 必须第一回合马上移动到 $4$ 才能确保获胜。例如，若 Jerry 从 $1$ 通过 $(1\to 4)$ 直接到 $4$，而 Tom 选择留在 $3$，则 Jerry 会在第一回合到达 $4$ 并获胜。因此 $f(1,3)=f(2,3)=1$。 - 若 $x=1,3$ 且 $y=2$，Tom 也必须第一回合移动到 $4$，$f(1,2)=f(3,2)=1$。 - 若 $x=2,3$ 且 $y=1$，Tom 也必须第一回合移动到 $4$，$f(2,1)=f(3,1)=1$。 由 ChatGPT 5 翻译