gistfile1.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author itahiri
 */
public class ProblemC {


    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        long ret1 = 0;
        long ret2 = 1;        
        
        int n = in.nextInt();
        
        int cost[] = new int[n+1];
        
        for (int i = 1; i < cost.length; i++) {
            cost[i] = in.nextInt();            
        }
        
        int m = in.nextInt();
        
        
        int nodei[] = new int[m+1];
        int nodej[] = new int[m+1];
        
        for (int i = 1; i < nodej.length; i++) {
            
            nodei[i] = in.nextInt();
            nodej[i] = in.nextInt();
            
        }
        
        int component[] = new int[n + 1];
        
        ProblemC.stronglyConnectedComponents(n, m, nodei, nodej, component);
        
        int[] minCost = new int[component[0]+1];
        Arrays.fill(minCost, 1000000007);
        
        int[] number = new int[component[0]+1];
                
        for (int i = 1; i < cost.length; i++) {
            
            int ci = component[i];
            if(cost[i] < minCost[ci]) {
                minCost[ci] = cost[i];
                number[ci] = 1;
            } else if(cost[i] == minCost[ci]) {
                number[ci]++;
            }                        
        }
        
        for (int c = 1; c <= component[0]; c++) {
            ret1 += minCost[c];
            ret2 = (ret2 * number[c]) % 1000000007;
        }
        
        System.out.print(ret1 + " " + ret2);
        
        
    }

    public static void stronglyConnectedComponents(int n, int m, int nodei[], int nodej[], int component[]) {

        int i, j, k, series, stackpointer, numcomponents, p, q, r;
        int backedge[] = new int[n + 1];
        int parent[] = new int[n + 1];
        int sequence[] = new int[n + 1];
        int stack[] = new int[n + 1];
        int firstedges[] = new int[n + 2];
        int endnode[] = new int[m + 1];
        boolean next[] = new boolean[n + 1];

        boolean trace[] = new boolean[n + 1];
        boolean fresh[] = new boolean[m + 1];
        boolean skip, found;
// set up the forward star representation of the graph 
        firstedges[1] = 0;
        k = 0;
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= m; j++) {
                if (nodei[j] == i) {
                    k++;
                    endnode[k] = nodej[j];
                }
            }
            firstedges[i + 1] = k;
        }
        for (j = 1; j <= m; j++) {
            fresh[j] = true;
        }
// initialize
        for (i = 1; i <= n; i++) {
            component[i] = 0;
            parent[i] = 0;
            sequence[i] = 0;
            backedge[i] = 0;
            next[i] = false;
            trace[i] = false;
        }
        series = 0;
        stackpointer = 0;
        numcomponents = 0;
// choose an unprocessed node not in the stack 
        while (true) {
            p = 0;
            while (true) {
                p++;
                if (n < p) {
                    component[0] = numcomponents;
                    return;
                }
                if (!trace[p]) {
                    break;
                }
            }
            series++;
            sequence[p] = series;
            backedge[p] = series;
            trace[p] = true;
            stackpointer++;
            stack[stackpointer] = p;
            next[p] = true;
            while (true) {
                skip = false;
                for (q = 1; q <= n; q++) {

    // find an unprocessed edge (p,q)
                    found = false;
                    for (i = firstedges[p] + 1; i <= firstedges[p + 1]; i++) {
                        if ((endnode[i] == q) && fresh[i]) { // mark the edge as processed 
                            fresh[i] = false;
                            found = true;
                            break;
                        }
                    }
                    if (found) {
                        if (!trace[q]) {
                            series++;
                            sequence[q] = series;
                            backedge[q] = series;
                            parent[q] = p;
                            trace[q] = true;
                            stackpointer++;
                            stack[stackpointer] = q;
                            next[q] = true;
                            p = q;
                        } else {
                            if (trace[q]) {
                                if (sequence[q] < sequence[p] && next[q]) {
                                    backedge[p] = (backedge[p] < sequence[q]) ? backedge[p] : sequence[q];
                                }
                            }
                        }
                        skip = true;
                        break;
                    }
                }
                if (skip) {
                    continue;
                }
                if (backedge[p] == sequence[p]) {
                    numcomponents++;
                    while (true) {
                        r = stack[stackpointer];
                        stackpointer--;
                        next[r] = false;
                        component[r] = numcomponents;
                        if (r == p) {
                            break;
                        }
                    }
                }
                if (parent[p] != 0) {
                    backedge[parent[p]] = (backedge[parent[p]] < backedge[p]) ? backedge[parent[p]] : backedge[p];

                    p = parent[p];
                } else {
                    break;
                }
            }
        }
    }

}