E. Transitive Graph
dfs and similar; dp; dsu; graphs; implementation
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.
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\).
For each test case, output two numbers — the length of the longest simple path in \(H\) and the minimal possible value of such path.
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.