给你一个有向无环图,其中有 $$$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$$$。