← 返回题目列表

Codeforces · 1616/G

G. 只需添加一条边

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

给你一个有向无环图,其中有 $$$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 \to b$$$。边 $$$a \to b$$$ 不会出现多次。

输出

对于每个测试用例,打印一个整数:顶点对 $$$x$$$、$$$y$$$、$$$x > y$$$ 的数量,这样将边 $$$x \to y$$$ 添加到图中后,它就有一条哈密顿路径。

示例

输入 #1

3
3 2
1 2
2 3
4 3
1 2
3 4
1 4
4 4
1 3
1 4
2 3
3 4

输出 #1

3
1
4

注意

在第一个示例中,任何满足 $$$x > y$$$ 的边 $$$x \to 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$$$。