CF1900E.Transitive Graph

You are given a directed graph $G$ with $n$ vertices and $m$ edges between them.

Initially, graph $H$ is the same as graph $G$. Then you decided to perform the following actions:

• If there exists a triple of vertices $a$, $b$, $c$ of $H$, such that there is an edge from $a$ to $b$ and an edge from $b$ to $c$, but there is no edge from $a$ to $c$, add an edge from $a$ to $c$.
• Repeat the previous step as long as there are such triples.

Note that the number of edges in $H$ can be up to $n^2$ after performing the actions.

You also wrote some values on vertices of graph $H$. More precisely, vertex $i$ has the value of $a_i$ written on it.

Consider a simple path consisting of $k$ distinct vertices with indexes $v_1, v_2, \ldots, v_k$. The length of such a path is $k$. The value of that path is defined as $\sum_{i = 1}^k a_{v_i}$.

A simple path is considered the longest if there is no other simple path in the graph with greater length.

Among all the longest simple paths in $H$, find the one with the smallest value.

给你一个包含 $n$ 个顶点和 $m$ 条有向边的有向图 $G$。

初始时，图 $H$ 与图 $G$ 完全相同。随后你决定执行如下操作：

• 若图 $H$ 中存在三个顶点 $a$、$b$、$c$，使得存在从 $a$ 到 $b$ 的边以及从 $b$ 到 $c$ 的边，但不存在从 $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$ 的所有最长简单路径中，找出值最小的一条。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n,m \le 2 \cdot 10^5$) — the number of vertices and the number of edges.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the numbers written on the vertices of graph $H$.

The $i$-th of the next $m$ lines contains two integers $v_i$ and $u_i$ ($1 \le v_i, u_i \le n$) — meaning that there is an edge going from vertex $v_i$ to vertex $u_i$ in graph $G$. Note that edges are directed. Also note that the graph may have self-loops and multiple edges.

It is guaranteed that neither the sum of $n$ nor the sum of $m$ over all test cases exceeds $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n,m \le 2 \cdot 10^5$）—— 分别表示图 $H$ 的顶点数和边数。

第二行包含 $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$）—— 表示图 $G$ 中存在一条从顶点 $v_i$ 指向顶点 $u_i$ 的有向边。注意：边是有向的；此外，图可能包含自环和重边。

保证所有测试用例的 $n$ 之和以及 $m$ 之和均不超过 $2 \cdot 10^5$。

For each test case, output two numbers — the length of the longest simple path in $H$ and the minimal possible value of such path.

对于每个测试用例，输出两个数——图 $H$ 中最长简单路径的长度，以及该长度下路径的最小可能值。

In the first test case, the longest path in both graphs is $1 \to 3 \to 4 \to 5 \to 2$. As the path includes all vertices, the minimal possible value of the longest path is the sum of values on all vertices, which is $12$.

In the second test case, the longest possible path is $1 \to 2 \to 3 \to 4 \to 6 \to 7$. As there are no longest paths with vertex $5$ in them, this path has the minimal possible value of $5\,999\,999\,995$.

In the third test case, it can be proven that there is no path longer than $11$ and that the value of the longest path cannot be less than $37$. Also, notice that the given graph has both self-loops and multiple edges.

在第一个测试用例中，两个图中的最长路径均为 $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$。此外，请注意所给图中既存在自环，也存在重边。