给你一个有向图 $$$G$$$,其中有 $$$n$$$ 个顶点以及它们之间的 $$$m$$$ 边。
最初,图 $$$H$$$ 与图 $$$G$$$ 相同。然后您决定执行以下操作:
- 如果存在 $$$H$$$ 的三重顶点 $$$a$$$、$$$b$$$、$$$c$$$,则存在从 $$$a$$$ 到 $$$b$$$ 的边以及从 $$$b$$$ 到 $$$c$$$ 的边,但没有从 $$$a$$$ 到 $$$a$$$ 的边$$$c$$$,添加一条从 $$$a$$$ 到 $$$c$$$ 的边。
- 只要存在这样的三元组,就重复上一步。
请注意,执行操作后,$$$H$$$ 中的边数最多可达 $$$n^2$$$。
您还在图 $$$H$$$ 的顶点上写了一些值。更准确地说,顶点 $$$i$$$ 上写有 $$$a_i$$$ 的值。
考虑一条由 $$$k$$$ 不同顶点组成的简单路径,索引为 $$$v_1, v_2, \ldots, v_k$$$。这样一条路径的长度是$$$k$$$。该路径的值定义为 $$$\sum_{i = 1}^k a_{v_i}$$$。
如果图中没有其他长度更大的简单路径,则简单路径被认为是最长的。
在 $$$H$$$ 中所有最长的简单路径中,找到具有最小值的路径。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$) - 顶点数和边数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) - 写在图 $$$H$$$ 顶点上的数字。
接下来的 $$$m$$$ 行中的第 $$$i$$$ 包含两个整数 $$$v_i$$$ 和 $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) - 意味着图中有一条从顶点 $$$v_i$$$ 到顶点 $$$u_i$$$ 的边$$$G$$$。请注意,边是有向的。另请注意,该图可能具有自环和多条边。
保证所有测试用例的 $$$n$$$ 总和和 $$$m$$$ 总和都不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出两个数字 - $$$H$$$ 中最长简单路径的长度以及该路径的最小可能值。
示例
输入 #1
3 5 6 2 2 4 1 3 1 2 1 3 2 4 3 4 4 5 5 2 7 7 999999999 999999999 999999999 999999999 1000000000 999999999 1000000000 1 2 2 3 3 4 4 1 4 5 4 6 6 7 14 22 2 3 5 7 3 4 1 4 3 4 2 2 5 1 1 2 2 3 2 4 3 1 4 4 4 5 5 6 5 6 5 12 6 7 6 8 7 5 7 7 7 9 8 4 9 11 10 9 11 10 11 10 12 13 13 14 14 12
输出 #1
5 12 6 5999999995 11 37
注意
在第一个测试用例中,两个图中的最长路径都是 $$$1 \to 3 \to 4 \to 5 \to 2$$$。由于路径包含所有顶点,因此最长路径的最小可能值为所有顶点上的值之和,即$$$12$$$。
在第二个测试用例中,最长的可能路径是 $$$1 \to 2 \to 3 \to 4 \to 6 \to 7$$$。由于不存在包含顶点 $$$5$$$ 的最长路径,因此该路径的最小可能值为 $$$5\,999\,999\,995$$$。
在第三个测试用例中,可以证明不存在超过$$$11$$$的路径,并且最长路径的值不能小于$$$37$$$。另外,请注意给定的图既有自环又有多重边。