You are given a rooted tree with n vertices, the root of the tree is the vertex 1. Each vertex has some non-negative price. A leaf of the tree is a non-root vertex that has degree 1.

Arkady and Vasily play a strange game on the tree. The game consists of three stages. On the first stage Arkady buys some non-empty set of vertices of the tree. On the second stage Vasily puts some integers into all leaves of the tree. On the third stage Arkady can perform several (possibly none) operations of the following kind: choose some vertex v he bought on the first stage and some integer x, and then add x to all integers in the leaves in the subtree of v. The integer x can be positive, negative of zero.

A leaf a is in the subtree of a vertex b if and only if the simple path between a and the root goes through b.

Arkady's task is to make all integers in the leaves equal to zero. What is the minimum total cost s he has to pay on the first stage to guarantee his own win independently of the integers Vasily puts on the second stage? Also, we ask you to find all such vertices that there is an optimal (i.e. with cost s) set of vertices containing this one such that Arkady can guarantee his own win buying this set on the first stage.

Input

The first line contains a single integer n (2 ≤ n ≤ 200 000) — the number of vertices in the tree.

The second line contains n integers c_1, c_2, …, c_n (0 ≤ c_i ≤ 10^9), where c_i is the price of the i-th vertex.

Each of the next n - 1 lines contains two integers a and b (1 ≤ a, b ≤ n), denoting an edge of the tree.

Output

In the first line print two integers: the minimum possible cost s Arkady has to pay to guarantee his own win, and the number of vertices k that belong to at least one optimal set.

In the second line print k distinct integers in increasing order the indices of the vertices that belong to at least one optimal set.

Examples

Input


5
5 1 3 2 1
1 2
2 3
2 4
1 5


Output


4 3
2 4 5 


Input


3
1 1 1
1 2
1 3


Output


2 3
1 2 3 

Note

In the second example all sets of two vertices are optimal. So, each vertex is in at least one optimal set.
import java.io.*;
import java.util.*;

public class CF_1120D {
    static final String name = "CF_1120D";
    static final boolean test = new File(name + ".in").exists();

    static ArrayList<ArrayList<Integer>> adj;
    static long[] c;
    public static void main(String args[]) throws Exception {
        BufferedScanner in = new BufferedScanner(test ? new FileInputStream(name + ".in") : System.in);
        BufferedPrinter out = new BufferedPrinter(test ? new FileOutputStream(name + ".out") : System.out);

        int n = in.nextInt();
        c = in.nextNL(n);

        // Build tree
        adj = get2D(n);
        for(int i = 0; i < n - 1; i++){
            int u = in.nextInt() - 1, v = in.nextInt() - 1;
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        Data data = ans(0, -1);
        fin.addAll(data.nums);

        long cost = data.min + data.tot;
        out.println(cost + " " + fin.size());

        Collections.sort(fin);
        for(Integer v: fin) out.print((v + 1) + " ");

        out.close();
        in.close();
    }

    static class Data{
        long min;
        long tot;
        ArrayList<Integer> nums;

        Data(long val, int idx, long tot){
            this.min = val;
            this.tot = tot;

            this.nums = new ArrayList<>();
            nums.add(idx);
        }

        void add(int idx) {
            if(min > c[idx]){
                nums.clear();
                nums.add(idx);

                min = c[idx];
            }else if(min == c[idx]){
                nums.add(idx);
            }
        }
    }

    static ArrayList<Integer> fin = new ArrayList<>();
    static Data ans(int curr, int p){
        int deg = adj.get(curr).size();

        // Implicitly add a parent for the root
        if(p == -1) deg++;

        // If this is a leaf node
        if(deg == 1) return new Data(c[curr], curr, 0);

        // If exactly one child
        if(deg == 2) {
            for(Integer v: adj.get(curr)){
                if(v != p){
                    Data data = ans(v, curr);

                    // Add our idx to the running min
                    data.add(curr);

                    return data;
                }
            }
        }

        // Collect all data from children
        ArrayList<Data> ds = new ArrayList<>();
        for(Integer v: adj.get(curr)) {
            if(v == p) continue;
            ds.add(ans(v, curr));
        }

        // Find the data with maximum min value
        Collections.sort(ds, (a, b) -> Long.compare(a.min, b.min));
        Data ret = ds.remove(ds.size() - 1);

        // Add up all of the used mins / tots
        for(Data d: ds){
            if(d.min == ret.min) {
                fin.addAll(ret.nums);
                ret.nums.clear();
            }

            fin.addAll(d.nums);
            ret.tot += d.tot + d.min;
        }

        // Add our idx to the running min
        ret.add(curr);
        return ret;
    }

    /**
     * My template below. FastIO and utility functions.
     * Minimized with https://codebeautify.org/javaviewer.
     */

    // @formatter:off
    static<T>ArrayList<ArrayList<T>>get2D(int n){ArrayList<ArrayList<T>>ret=new ArrayList<>();for(int i=0;i<n;i++)ret.add(new ArrayList<>());return ret;}
    static void force(boolean condition){if(!condition)throw new IllegalStateException();}
    static void debug(Object obj){if(obj instanceof long[][]){for(long[]a:(long[][])obj)System.out.println(Arrays.toString(a));}
    else if(obj instanceof int[][]){for(int[]a:(int[][])obj)System.out.println(Arrays.toString(a));}
    else if(obj instanceof char[][]){for(char[]a:(char[][])obj)System.out.println(Arrays.toString(a));}
    else if(obj instanceof boolean[][]){for(boolean[]a:(boolean[][])obj)System.out.println(Arrays.toString(a));}
    else if(obj instanceof long[]){System.out.println(Arrays.toString((long[])obj));}
    else if(obj instanceof int[]){System.out.println(Arrays.toString((int[])obj));}
    else if(obj instanceof char[]){System.out.println(Arrays.toString((char[])obj));}
    else if(obj instanceof boolean[]){System.out.println(Arrays.toString((boolean[])obj));}
    else{System.out.println(obj);}}
    static class BufferedPrinter{PrintWriter out;BufferedPrinter(OutputStream out){this(new OutputStreamWriter(out));}
    BufferedPrinter(Writer out){this.out=new PrintWriter(new BufferedWriter(out));}
    void print(Object...os){for(int i=0;i<os.length;i++){if(i!=0)out.print(' ');out.print(os[i]);}}
    void println(Object...os){print(os);out.println();}
    void close(){out.close();}
    void flush(){out.flush();}}
    static class BufferedScanner{private final InputStream in;private final byte[]buf=new byte[1<<13];int pos,count;BufferedScanner(InputStream in)throws IOException{this.in=in;}
    long nextLong()throws IOException{return Long.parseLong(next());}
    int[]nextN(int n)throws IOException{int[]ret=new int[n];for(int i=0;i<n;i++)ret[i]=this.nextInt();return ret;}
    long[]nextNL(int n)throws IOException{long[]ret=new long[n];for(int i=0;i<n;i++)ret[i]=this.nextLong();return ret;}
    private int read(){if(count==-1)err();try{if(pos>=count){pos=0;count=in.read(buf);if(count<=0)return-1;}}catch(IOException e){err();}
    return buf[pos++];}
    private static boolean isSpace(int c){return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;}
    private int readSkipSpace(){int ret;do{ret=read();}while(isSpace(ret));return ret;}
    int nextInt(){int sign=1;int c=readSkipSpace();if(c=='-'){sign=-1;c=read();}
    int ret=0;do{if(c<'0'||c>'9')err();ret=ret*10+c-'0';c=read();}while(!isSpace(c));return sign*ret;}
    String next(){StringBuilder sb=new StringBuilder();int c=readSkipSpace();do{sb.append((char)c);c=read();}while(!isSpace(c));return sb.toString();}
    private void err(){throw new InputMismatchException();}
    void close()throws IOException{in.close();}}
    // @formatter:on
}
