CF2187C.Jerry and Tom

Jerry and Tom are playing a game on a directed graph $G$ with $n$ vertices, numbered from $1$ to $n$. For every vertex $1 \le u \lt n$, there is a directed edge from $u$ to $u+1$. In addition, there are $m$ extra directed edges. The $i$-th extra edge goes from $u_i$ to $v_i$, where $1 \le u_i \lt v_i \le n$.

The graph $G$ has the following special property: there do not exist two directed edges $(u_i\to v_i)$ and $(u_j\to v_j)$ such that $u_i \lt u_j \lt v_i \lt v_j$.

At the beginning of the game, Jerry and Tom stand on vertices $x$ and $y$, respectively, where $x \ne y$. The game proceeds in turns. In each turn, the players behave according to the following rules, with Jerry going first, followed by Tom:

• Jerry must choose one outgoing edge from his current vertex and move along it to its end. If his current vertex has no outgoing edges, he stays where he is.
• Tom may choose one outgoing edge from his current vertex and move along it to its end, or choose not to move and stay where he is.

If at the end of any turn, Jerry and Tom are at the same vertex (including at vertex $n$), the game ends immediately and Tom wins. Otherwise, if Jerry is initially at vertex $n$, or reaches vertex $n$ at the end of any turn, Jerry wins.

Note that if after a turn, both Jerry and Tom are at vertex $n$, then Tom wins.

Throughout the entire game, both players know each others' locations.

It can be proven that the game will end in a finite number of turns.

For a pair of integers $1 \le x,y \le n$, $x \ne y$, define $f(x,y)$ as follows:

• Jerry and Tom will play a game, where Jerry starts at vertex $x$ and Tom starts at vertex $y$. Tom wants to win, but he also wants to minimise the number of times he actually moves (that is, the number of turns in which he changes his vertex; staying still does not count as a move). Assuming both players play optimally, let $f(x,y)=0$ if Tom cannot win; otherwise, let $f(x,y)$ be the minimum number of moves Tom has to make in order to force a win. If Tom wins under optimal play, Jerry will still try to maximize the number of moves Tom has to make.

Compute $$\sum\limits_{1 \le x,y \le n, x \ne y}f(x,y).$$

杰瑞和汤姆正在一张有 $n$ 个顶点（编号为 $1$ 到 $n$）的有向图 $G$ 上进行一场游戏。对每个顶点 $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$。

游戏开始时，杰瑞和汤姆分别位于顶点 $x$ 和 $y$，其中 $x \ne y$。游戏按回合进行，杰瑞先手，随后是汤姆。每回合中，双方按如下规则行动：

• 杰瑞必须从其当前顶点出发，选择一条出边，并沿该边移动至其终点；若其当前顶点无出边，则他停留在原地。
• 汤姆可选择从其当前顶点出发，选择一条出边并沿该边移动至其终点；也可选择不移动而停留在原地。

若在某回合结束时，杰瑞与汤姆处于同一顶点（包括顶点 $n$），则游戏立即结束，汤姆获胜。否则，若杰瑞初始位置即为顶点 $n$，或在某回合结束时到达顶点 $n$，则杰瑞获胜。

注意：若某回合结束时，杰瑞与汤姆均位于顶点 $n$，则汤姆获胜。

在整个游戏中，双方始终知晓彼此的当前位置。

可以证明，该游戏必在有限步内结束。

对任意整数对 $1 \le x,y \le n$ 且 $x \ne y$，定义函数 $f(x,y)$ 如下：

• 杰瑞与汤姆进行一局游戏，杰瑞起始于顶点 $x$，汤姆起始于顶点 $y$。汤姆的目标是获胜，同时他还希望最小化自己实际移动的次数（即改变所在顶点的回合数；停留原地不计为一次移动）。假设双方均采取最优策略，若汤姆无法获胜，则令 $f(x,y) = 0$；否则，令 $f(x,y)$ 为汤姆为确保获胜所需的最少移动次数。若在最优策略下汤姆能获胜，则杰瑞仍会尽力使汤姆所需移动次数最大化。

计算

$$\sum\limits_{1 \le x,y \le n,\, x \ne y}f(x,y).$$

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $0 \le m \le n-2$), representing the number of vertices and the number of extra edges, respectively.

The $i$-th of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i,v_i \le n$, $u_i + 1 \lt v_i$), representing an extra edge. It is guaranteed that for any ordered pair of vertices $(u,v)$, there exists at most one edge from $u$ to $v$. It is guaranteed that there do not exist two directed edges $(u_i\to v_i)$ and $(u_j\to v_j)$ such that $u_i \lt u_j \lt v_i \lt v_j$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$0 \le m \le n-2$），分别表示顶点数和额外边的数量。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i,v_i \le n$，且 $u_i + 1 \lt v_i$），表示一条额外边。保证对于任意有序顶点对 $(u,v)$，至多存在一条从 $u$ 到 $v$ 的边。还保证不存在两条有向边 $(u_i\to v_i)$ 和 $(u_j\to v_j)$，使得 $u_i \lt u_j \lt v_i \lt v_j$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output an integer representing the value of the expression.

对于每个测试用例，输出一个整数，表示该表达式的值。

In the first test case:

• $x=1$, $y=2$: Jerry is forced to move to $2$ on the first turn. Then, Tom can wait at $2$. At the end of the first turn, both Jerry and Tom are at $2$, and thus, $f(1,2)=0$ as Tom can win without ever moving.
• $x=2$, $y=1$: Jerry is at $n=2$ at the beginning; Tom cannot force a win. Thus, $f(2,1)=0$.

In the third test case, the pairs of $(x,y)$ such that Tom wins are as follows:

• For $x=1,2,3$ and $y=4$. No matter where Jerry moves to, Tom can stay at $4$ until Jerry reaches $4$. Tom can win without ever moving. $f(1,4)=f(2,4)=f(3,4)=0$.
• For $x=1,2$ and $y=3$, no matter where Jerry moves to on the first turn, Tom has to move to $4$ on the first turn to guarantee a win. For example, if Jerry starts at $1$ and moves to $4$ through the edge $(1 \to 4)$, but Tom chooses to stay at $3$ on the first turn, Jerry reaches $4$ at the end of the first turn, winning the game. Thus, $f(1,3)=f(2,3)=1$.
• For $x=1,3$ and $y=2$, Tom also has to move to $4$ on the first turn to guarantee a win; $f(1,2)=f(3,2)=1$.
• For $x=2,3$ and $y=1$, Tom still has to move to $4$ on the first turn to guarantee a win; $f(2,1)=f(3,1)=1$.

在第一个测试用例中：

• $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 到达 $4$。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$。