← 返回题目列表

Codeforces · 427/C

C. 检查站

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

你的城市有 n 个路口。路口之间有 m 条单向道路。作为市长,你必须确保所有路口的安全。

为了确保安全,你必须建立一些警察检查站。检查站只能建在路口。如果 i = j,或者警察巡逻车可以从 i 前往 j,然后返回 i,则 i 路口的检查站可以保护 j 路口。

建造检查站需要花费一些钱。由于城市的某些区域比其他区域更昂贵,因此在某些路口建立检查站可能比其他路口花费更多的钱。

你必须确定确保所有路口安全所需的最低可能资金。此外,您还必须找到以最低价格确保安全的方法数量以及最少数量的检查站。如果其中一个路口包含检查站而另一个路口不包含检查站,则两种方式是不同的。

输入

在第一行中,您将得到一个整数 n,即结点数量 (1 ≤ n ≤ 105)。在下一行中,将给出 n 个空格分隔的整数。第 i 个整数是在第 i 个路口建立检查站的成本(成本将是非负数且不会超过 109)。

下一行将包含一个整数 m (0 ≤ m ≤ 3·105)。接下来的 m 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n; u ≠ v)。一对 ui, vi 表示有一条从 ui 到 vi 的单向路。同一方向的两个节点之间不会有多于一条道路。

输出

打印两个以空格分隔的整数。第一个是确保所有路口安全所需的最低限度的资金。第二个是可以确保安全性的方法数模 1000000007 (109 + 7)。

示例

输入 #1

3
1 2 3
3
1 2
2 3
3 2

输出 #1

3 1

输入 #2

5
2 8 0 6 0
6
1 4
1 3
2 4
3 4
4 5
5 1

输出 #2

8 2

输入 #3

10
1 3 2 2 1 3 1 4 10 10
12
1 2
2 3
3 1
3 4
4 5
5 6
5 7
6 4
7 3
8 9
9 10
10 9

输出 #3

15 6

输入#4

2
7 91
2
1 2
2 1

输出#4

7 1