← 返回题目列表

Codeforces · 2187/C

C. 杰瑞和汤姆

中文机器翻译题面 查看原题

Jerry 和 Tom 正在有向图 $$$G$$$ 上玩游戏,该图有 $$$n$$$ 个顶点,编号从 $$$1$$$ 到 $$$n$$$。对于每个顶点 $$$1 \le u \lt n$$$,都有一条从 $$$u$$$ 到 $$$u+1$$$ 的有向边。此外,还有 $$$m$$$ 额外的有向边。第 $$$i$$$ 额外边从 $$$u_i$$$ 到 $$$v_i$$$,其中 $$$1 \le u_i \lt v_i \le n$$$。

图 $$$G$$$ 具有以下特殊属性:有 不存在 两条有向边 $$$(u_i\to v_i)$$$ 和 $$$(u_j\to v_j)$$$ 使得 $$$u_i \lt u_j \lt v_i \lt v_j$$$。

游戏开始时,杰瑞和汤姆分别站在顶点 $$$x$$$ 和 $$$y$$$ 上,其中 $$$x \ne y$$$。游戏轮流进行。在每个回合中,玩家按照以下规则行事,杰瑞先行,汤姆紧随其后:

  • 杰瑞 必须 从当前顶点选择一条出边并沿其移动到终点。如果他当前的顶点没有出边,他就会留在原处。
  • 汤姆 可能 从当前顶点选择一条出边并沿着它移动到终点, or 选择不动并留在原地。

如果在任何回合结束时,杰瑞和汤姆位于同一顶点(包括顶点 $$$n$$$),游戏立即结束,汤姆获胜。否则,如果杰瑞最初位于顶点$$$n$$$,或在任何回合结束时到达顶点$$$n$$$,则杰瑞获胜。

请注意,如果转弯后,Jerry 和 Tom 都位于顶点 $$$n$$$,则 汤姆获胜.

纵观整场比赛, 两位玩家都知道 彼此的位置。

可以证明游戏会在有限的回合内结束。

对于一对整数 $$$1 \le x,y \le n$$$, $$$x \ne y$$$,定义 $$$f(x,y)$$$ 如下:

  • Jerry 和 Tom 将玩一个游戏,Jerry 从顶点 $$$x$$$ 开始,Tom 从顶点 $$$y$$$ 开始。汤姆想赢,但他也想尽量减少他实际移动的次数(即他改变顶点的回合数; 保持静止不算移动)。假设两个玩家都发挥最佳状态,如果 Tom 无法获胜,则令 $$$f(x,y)=0$$$;否则,令 $$$f(x,y)$$$ 为汤姆为了强行获胜而必须采取的最小步数。如果汤姆在最佳玩法下获胜,杰瑞仍然会尝试最大化汤姆必须采取的行动数量。

计算 $$\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$$$ 行的第 $$$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$$$。

输出

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

示例

输入
复制

5
2 0
3 1
1 3
4 2
2 4
1 4
5 1
1 4
8 3
1 4
5 8
2 4

输出
复制

0
2
6
3
23

注意

在第一个测试用例中:

  • $$$x=1$$$, $$$y=2$$$:杰瑞被迫在第一回合移动到$$$2$$$。然后,汤姆可以在 $$$2$$$ 处等待。在第一回合结束时,杰瑞和汤姆都处于$$$2$$$,因此,$$$f(1,2)=0$$$,因为汤姆无需移动即可获胜。
  • $$$x=2$$$, $$$y=1$$$:杰瑞一开始位于$$$n=2$$$;汤姆无法强行获胜。因此,$$$f(2,1)=0$$$。

在第三个测试用例中,使得 Tom 获胜的 $$$(x,y)$$$ 对如下:

  • 对于 $$$x=1,2,3$$$ 和 $$$y=4$$$。无论杰瑞搬到哪里,汤姆都可以保持$$$4$$$,直到杰瑞达到$$$4$$$。汤姆不用动就能获胜。 $$$f(1,4)=f(2,4)=f(3,4)=0$$$。
  • 对于 $$$x=1,2$$$ 和 $$$y=3$$$,无论 Jerry 在第一回合移动到哪里,Tom 都必须在第一回合移动到 $$$4$$$ 才能保证获胜。例如,如果杰瑞从 $$$1$$$ 开始,通过边缘 $$$(1 \to 4)$$$ 移动到 $$$4$$$,但汤姆选择在第一回合保持在 $$$3$$$,则杰瑞在第一回合结束时达到 $$$4$$$,赢得游戏。因此,$$$f(1,3)=f(2,3)=1$$$。
  • 对于 $$$x=1,3$$$ 和 $$$y=2$$$,汤姆还必须在第一回合移动到 $$$4$$$ 才能保证获胜; $$$f(1,2)=f(3,2)=1$$$。
  • 对于 $$$x=2,3$$$ 和 $$$y=1$$$,Tom 仍然需要在第一回合移动到 $$$4$$$ 才能保证获胜; $$$f(2,1)=f(3,1)=1$$$。