310858: CF1900E. Transitive Graph

E. Transitive Graphtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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

ExampleInput

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

Output

5 12
6 5999999995
11 37

Note

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.

题目大意：给定一个有n个顶点和m条边的有向图G。最初，图H与图G相同。然后决定执行以下操作：
1. 如果存在H的三个顶点a、b、c，使得从a到b有一条边，从b到c有一条边，但从a到c没有边，那么从a到c添加一条边。
2. 重复上一步，直到没有这样的三元组。

注意，执行操作后，H中的边数可以达到n^2。

你在图H的顶点上写了一些值。更准确地说，顶点i上写的是a_i的值。

考虑一个由k个不同的顶点组成的简单路径，索引为v_1，v_2，...，v_k。这样的路径的长度是k。该路径的值定义为sum_{i = 1}^k a_{v_i}。

如果不存在长度更长的简单路径，则认为简单路径是最长的。

在H的所有最长简单路径中，找到值最小的路径。

输入数据格式：
每个测试包含多个测试用例。第一行包含测试用例数t（1 <= t <= 10^4）。接下来是测试用例的描述。
每个测试用例的第一行包含两个整数n和m（1 <= n，m <= 2 * 10^5）——顶点数和边数。
第二行包含n个整数a_1，a_2，...，a_n（0 <= a_i <= 10^9）——图H顶点上的数字。
接下来的m行中的第i行包含两个整数v_i和u_i（1 <= v_i，u_i <= n）——表示图G中从顶点v_i到顶点u_i有一条边。注意，边是有向的。还要注意，图可能有自环和多重边。
保证所有测试用例的n之和和m之和不超过2 * 10^5。

输出数据格式：
对于每个测试用例，输出两个数字——H中最长简单路径的长度和这种路径的最小可能值。题目大意：给定一个有n个顶点和m条边的有向图G。最初，图H与图G相同。然后决定执行以下操作： 1. 如果存在H的三个顶点a、b、c，使得从a到b有一条边，从b到c有一条边，但从a到c没有边，那么从a到c添加一条边。 2. 重复上一步，直到没有这样的三元组。 注意，执行操作后，H中的边数可以达到n^2。 你在图H的顶点上写了一些值。更准确地说，顶点i上写的是a_i的值。 考虑一个由k个不同的顶点组成的简单路径，索引为v_1，v_2，...，v_k。这样的路径的长度是k。该路径的值定义为sum_{i = 1}^k a_{v_i}。 如果不存在长度更长的简单路径，则认为简单路径是最长的。 在H的所有最长简单路径中，找到值最小的路径。 输入数据格式： 每个测试包含多个测试用例。第一行包含测试用例数t（1 <= t <= 10^4）。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数n和m（1 <= n，m <= 2 * 10^5）——顶点数和边数。 第二行包含n个整数a_1，a_2，...，a_n（0 <= a_i <= 10^9）——图H顶点上的数字。 接下来的m行中的第i行包含两个整数v_i和u_i（1 <= v_i，u_i <= n）——表示图G中从顶点v_i到顶点u_i有一条边。注意，边是有向的。还要注意，图可能有自环和多重边。 保证所有测试用例的n之和和m之和不超过2 * 10^5。 输出数据格式： 对于每个测试用例，输出两个数字——H中最长简单路径的长度和这种路径的最小可能值。