You are given a tree with n vertices. Each vertex i has a value a_i associated with it.

Let us root the tree at some vertex v. The vertex v is called a distinctive root if the following holds: in all paths that start at v and end at some other node, all the values encountered are distinct. Two different paths may have values in common but a single path must have all distinct values.

Find the number of distinctive roots in the tree.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 2⋅10^5) — the number of vertices in the tree.

The next line contains n space-separated integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9).

The following n-1 lines each contain two space-separated integers u and v (1 ≤ u, v ≤ n), denoting an edge from u to v.

It is guaranteed that the edges form a tree.

Output

Print a single integer — the number of distinctive roots in the tree.

Examples

Input


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


Output


3

Input


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


Output


0

Note

In the first example, 1, 2 and 5 are distinctive roots.
import java.io.*;
import java.util.*;

/*
polyakoff
*/

public class Main {

    static FastReader in;
    static PrintWriter out;
    static Random rand = new Random();
    static final int oo = (int) 1e9 + 10;
    static final long OO = (long) 2e18 + 10;
    static final int MOD = (int) 1e9 + 7;

    static ArrayList<Integer>[] g;
    static int[] a, cntSubtr;
    static TreeMap<Integer, Integer> map;
    static boolean[] badSubtr, good;

    static void dfs1(int v, int from) {
        map.putIfAbsent(a[v], 0);
        map.put(a[v], map.get(a[v]) + 1);
        int last = map.get(a[v]);
        for (int to : g[v]) {
            if (to == from)
                continue;
            dfs1(to, v);
            cntSubtr[to] = map.get(a[v]) - last;
            last = map.get(a[v]);
            badSubtr[v] |= badSubtr[to];
            badSubtr[v] |= cntSubtr[to] > 0;
        }
    }

    static void dfs2(int v, int from, boolean ok) {
        int badCnt = 0;
        for (int to : g[v]) {
            if (to == from)
                continue;
            badCnt += badSubtr[to] ? 1 : 0;
        }
        good[v] = ok && (badCnt == 0) && (map.get(a[v]) == 1);
        for (int to : g[v]) {
            if (to == from)
                continue;
            boolean ok2 = ok && (badCnt == 0 || (badCnt == 1 && badSubtr[to])) && (map.get(a[v]) - cntSubtr[to] == 1);
            dfs2(to, v, ok2);
        }
    }

    static void solve() {
        int n = in.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        g = new ArrayList[n]; Arrays.setAll(g, i -> new ArrayList<>());
        for (int i = 0; i < n - 1; i++) {
            int v = in.nextInt() - 1;
            int u = in.nextInt() - 1;
            g[v].add(u);
            g[u].add(v);
        }

        cntSubtr = new int[n];
        map = new TreeMap<>();
        badSubtr = new boolean[n];
        dfs1(0, 0);
        good = new boolean[n];
        dfs2(0, 0, true);

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (good[i])
                ans++;
        }

        out.println(ans);

    }


    public static void main(String[] args) {
        in = new FastReader();
        out = new PrintWriter(System.out);
//        fileInputOutput();

        int T = 1;
//        T = in.nextInt();
        while (T-- > 0)
            solve();

        out.flush();
        out.close();
    }

    static void fileInputOutput() {
        try {
            in = new FastReader("input.txt");
            out = new PrintWriter(new FileOutputStream("output.txt"));
        } catch (FileNotFoundException e) {
            throw new RuntimeException(e);
        }
    }

    static void runInThread() {
        Thread thread = new Thread(null, () -> {
            int T = 1;
//            T = in.nextInt();
            while (T-- > 0)
                solve();
        }, "thread1", 1 << 28);
        thread.start();
        try {
            thread.join();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader() {
            this(System.in);
        }
        FastReader(String file) throws FileNotFoundException {
            this(new FileInputStream(file));
        }
        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }
        String nextLine() {
            String line;
            try {
                line = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }
    }
}