← 返回题目列表

Codeforces · 1900/E

E. 传递图

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

给你一个有向图 $$$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$$$。另外,请注意给定的图既有自环又有多重边。