传递图

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个带点权的有向图 $G$。不断执行传递闭包操作：若存在边 $a\to b$、$b\to c$ 而不存在边 $a\to c$，则加入边 $a\to c$，直至无法继续，得到图 $H$。

一条简单路径的长度是路径上的不同顶点数，权值是这些顶点的点权和。求 $H$ 中最长简单路径的长度，以及所有最长简单路径中的最小权值。

输入格式

第一行包含测试组数 $t$。每组先给出 $n,m$，随后给出 $n$ 个点权和 $m$ 条有向边。图中允许自环与重边。

输出格式

每组输出两个整数：最长简单路径长度与对应的最小权值。

样例输入 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\le t\le10^4$，$1\le n,m\le2\cdot10^5$；
• $0\le a_i\le10^9$；
• 所有测试组的 $n$ 之和、$m$ 之和分别不超过 $2\cdot10^5$。