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.awt.*;
import java.io.*;
import java.sql.Array;
import java.util.*;
import java.util.List;

public class Main {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(
                    new InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    static final int N=200005;
    static final int mod=1000000007;
    static final int INF=1000000009;
    static final int numBit=17;
    static FastReader r=new FastReader();
//    static PrintWriter pw = new PrintWriter(System.out);
    static class SegmentTree{
        int []seg;
        int []lazy;
        SegmentTree(int n){
            seg=new int[n*4];
            lazy=new int[n*4];
            Arrays.fill(seg,0);
            Arrays.fill(lazy,0);
        }
        public int min(int a,int b){
            return Math.min(a,b);
        }
        public void pushdown(int id){
            long val=lazy[id];
            seg[id*2]+=val;
            lazy[id*2]+=val;
            seg[id*2+1]+=val;
            lazy[id*2+1]+=val;
            lazy[id]=0;
        }
        public void update(int id,int l,int r,int beg,int fin,long val){
            if(fin<l||r<beg) return;
            if(beg<=l&&r<=fin){
                seg[id]+=val;
                lazy[id]+=val;
                return;
            }
            int mid=(l+r)>>1;
            pushdown(id);
            update(id*2,l,mid,beg,fin,val);
            update(id*2+1,mid+1,r,beg,fin,val);
            seg[id]=seg[id*2]+seg[id*2+1];
        }
        public int getSum(int id,int l,int r,int beg,int fin){
            if(fin<l||r<beg) return 0;
            if(beg<=l&&r<=fin){
                return seg[id];
            }
            int mid=(l+r)>>1;
            pushdown(id);
            return getSum(id*2,l,mid,beg,fin)+getSum(id*2+1,mid+1,r,beg,fin);
        }
    }
    static int[] timeIn=new int[N];
    static int[] timeOut=new int[N];
    static int[] pa=new int[N];
    static int time=-1;
    static void dfs(int u, int par){
        ++time;
        timeIn[u]=time;
        for(int x:v[u]){
            if(x==par) continue;
            pa[x]=u;
            dfs(x,u);
        }
        timeOut[u]=time;
    }

    static List<Integer> v[];

    public static void main(String[] args) throws IOException {
        int n=r.nextInt();
        boolean found=false;
        v=new List[n+1];
        for(int i=0;i<n+1;++i) v[i]=new ArrayList<>();
        List<Integer> pos[];
        int[] a=new int[n+1];
        for(int i=1;i<=n;++i) a[i]=r.nextInt();
        for(int i=0;i<n-1;++i){
            int x=r.nextInt();
            int y=r.nextInt();
            v[x].add(y);
            v[y].add(x);
            if(a[x]==a[y]) found=true;
        }
        if(found){
            System.out.println(0);
            System.exit(0);
        }
        dfs(1,0);
        Set<Integer> S=new HashSet<>();
        HashMap<Integer,Integer> maps=new HashMap();
        for(int i=1;i<=n;++i) S.add(a[i]);
//        System.out.println(S);
        pos=new List[S.size()];
//        System.out.println("size : "+S.size());
        for(int i=0;i<S.size();++i) pos[i]=new ArrayList<>();
        int id=0;
        for(int x:S){
            maps.put(x,id);
            ++id;
        }
        for(int i=1;i<=n;++i){
            pos[maps.get(a[i])].add(i);
        }
//        System.out.println("check ");
//        for(int i=0;i<pos.length;++i){
//            System.out.println("---------------------------------------");
//            System.out.println("#i = "+i);
//            System.out.println(pos[i]);
//        }
//        System.out.println("___________________________________________");
        SegmentTree tree1=new SegmentTree(n);
        SegmentTree tree2=new SegmentTree(n);
        for(int i=0;i< pos.length;++i){
            if(pos[i].size()<2) continue;
            for(int u:pos[i]){
                tree1.update(1,0,n-1,timeIn[u],timeIn[u],1);
                tree2.update(1,0,n-1,timeIn[u],timeIn[u],1);
            }
            for(int u:pos[i]){
                int cnt=0;
                for(int x:v[u]){
                    if(x==pa[u]){
                        int cnt1=pos[i].size()-tree1.getSum(1,0,n-1,timeIn[u],timeOut[u]);
                        if(cnt1>0) ++cnt;
                        else{
//                            System.out.println("in here");
                            tree2.update(1,0,n-1,timeIn[1],timeOut[1],1);
                            tree2.update(1,0,n-1,timeIn[u],timeOut[u],-1);
                        }
                    }
                    else{
//                        System.out.println("in here2");
                        int cnt1=tree1.getSum(1,0,n-1,timeIn[x],timeOut[x]);
                        if(cnt1>0) ++cnt;
                        else{
                            tree2.update(1,0,n-1,timeIn[x],timeOut[x],1);
                        }
                    }
                    if(cnt>=2){
                        System.out.println(0);
                        System.exit(0);
                    }
                }
            }
            for(int u:pos[i]){
                tree1.update(1,0,n-1,timeIn[u],timeIn[u],-1);
            }
        }
        int ans=0;
        for(int i=1;i<=n;++i){
            int cur=tree2.getSum(1,0,n-1,i-1,i-1);
            if(cur==0){
//                System.out.println("#"+i);
                ++ans;
            }
        }
        System.out.println(ans);
//        pw.close();
    }
}
