A16478 | 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$。

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