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.
// Jai Shree Ram  
  
#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC



template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}


const int N = 2e5+5;

vector<int>g[N];

map<int,int>mp[N];
map<int,int>cnt;
int a[N];
int pre[N];
void dfs(int u,int v){
        mp[u][a[u]]++;
        int found=-1;
        for(auto i:g[u]){
                if(i!=v){
                    dfs(i,u);
                    if(mp[i][a[u]]>0){
                        if(found!=-1){
                                cout<<0<<endl;exit(0);
                        }
                        found=i;
                    }
                    if(sz(mp[u])<sz(mp[i]))swap(mp[u],mp[i]);
                    for(auto j:mp[i]){
                            mp[u][j.x]+=j.y;
                    }
                }
        }
        if(cnt[a[u]]>1){
                if(mp[u][a[u]]==cnt[a[u]]){
                    pre[1]++,pre[found]--;
                }
                else if(mp[u][a[u]]==1){
                    pre[u]++;
                }
                else{
                        pre[1]++;
                }
        }
}


int ans=0;

void dfs2(int u,int v,int sum=0){
        sum+=pre[u];
        ans+=(sum==0);
        for(auto i:g[u]){
                if(i!=v)dfs2(i,u,sum);
        }
}       

int solve(){    
                int n;cin>>n;
                rep(i,1,n+1){
                    cin>>a[i];cnt[a[i]]++;
                }
                rep(i,0,n-1){
                    int a,b;cin>>a>>b;
                    g[a].pb(b);
                    g[b].pb(a);
                }
                dfs(1,1);
                dfs2(1,1,0);
                cout<<ans<<endl;

 return 0;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
 