ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5653: Checkposts

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：3 通过：3
提交提交记录统计Web Board

题目描述

您的城市有 n 个交汇点。交叉路口之间有m条单行道。作为市长，您必须确保所有路口的安全。
        为了确保安全，你必须建立一些警察检查站。检查站只能建在交汇点内。如果 i=j 或警察巡逻车可以从 i 转到 j，然后返回 i，则交叉路口 i 的检查站可以保护交叉路口 j。
        建立检查站需要一些钱。由于城市的某些地区比其他地区更昂贵，因此在某些路口建造检查站可能比其他路口花费更多的钱。
        您必须确定确保所有交汇点安全所需的最低可能资金。此外，您还必须找到确保最低价格和最少检查站数量安全性的方法数量。如果任何交汇点在其中一个交汇点中包含校验站，而在另一个交汇点中不包含校验站，则两种方式是不同的。
        Your city has n junctions. There are m one-way roads between the junctions. As a mayor of the city, you have to ensure the security of all the junctions.

        To ensure the security, you have to build some police checkposts. Checkposts can only be built in a junction. A checkpost at junction i can protect junction j if either i=j or the police patrol car can go to j from i and then come back to i.
        Building checkposts costs some money. As some areas of the city are more expensive than others, building checkpost at some junctions might cost more money than other junctions.
    You have to determine the minimum possible money needed to ensure the security of all the junctions. Also you have to find the number of ways to ensure the security in minimum price and in addition in minimum number of checkposts. Two ways are different if any of the junctions contains a checkpost in one of them and do not contain in the other.
Input
In the first line, you will be given an integer n, number of junctions (1≤n≤105). In the next line, n space-separated integers will be given. The ith integer is the cost of building checkpost at the ith junction (costs will be non-negative and will not exceed 109).
The next line will contain an integer m(0≤m≤3·105). And each of the next m lines contains two integers ui and vi(1≤ui,vi≤n;u≠v). A pair ui,vi means, that there is a one-way road which goes from ui to vi. There will not be more than one road between two nodes in the same direction.
Output
Print two integers separated by spaces. The first one is the minimum possible money needed to ensure the security of all the junctions. And the second one is the number of ways you can ensure the security modulo 1000000007 (109+7).
Examples
Input 
3
1 2 3
3
1 2
2 3
3 2
Output 
3 1
Input 
5
2 8 0 6 0
6
1 4
1 3
2 4
3 4
4 5
5 1
Output 
8 2
Input 
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
Output 
15 6
Input 
2
7 91
2
1 2
2 1
Output 
7 1

输入格式

在第一行中，您将获得一个整数 n，交汇点数（1≤n≤105).在下一行中，将给出 n 个空格分隔的整数。这ith整数是在ithi到 ith结点（成本将是非负的，不会超过）109).
下一行将包含一个整数m（0≤m≤3·105).接下来的 m 行中的每一行都包含两个整数在ui和在vi（1≤ui，vi≤n;U≠V).一对在ui，vi意味着有一条单行道从在ui自vi.同一方向的两个节点之间不会有多条道路。

输出格式

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

Examples

Input

3

1 2 3

3

1 2

2 3

3 2

Output

3 1

Input

5

2 8 0 6 0

6

1 4

1 3

2 4

3 4

4 5

5 1

Output

8 2

Input

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

Output

15 6

Input

2

7 91

2

1 2

2 1

Output

7 1

输入样例 复制 

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

输出样例 复制 

15 6

分类标签