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

long long n, l,val[200005],u,v,ans,cont,upd[200005],h[200005],sub[200005];
map<long long,vector<int> > opz;
map<int,int> conta[200005];
vector<vector<int>> adj;
int timer;
vector<int> tin, tout;
vector<vector<int>> up;

int prof;
void dfs(int v, int p)
{
	
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

	
    for (int u : adj[v]) {
        if (u != p){
			dfs(u, v);
			
			if(conta[u].size()>conta[v].size()){
				swap(conta[u],conta[v]);
			}
		}
    }
    
    for (int u : adj[v]) {
        if (u != p){
			for(auto i : conta[u]){
				conta[v][i.first]+=i.second;
			}
		}
    }
	
	sub[v]=conta[v][val[v]];
	conta[v][val[v]]++;
    tout[v] = ++timer;
}

bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

void preprocess(int root) {
    tin.resize(n+1);
    tout.resize(n+1);
    timer = 0;
    l = ceil(log2(n+1));
    up.assign(n+1, vector<int>(l + 1));
    dfs(root, root);
}

bool comp(int x,int y){
	return h[x]<h[y];
}

void calc(int nodo,int last,int num){
	if(upd[nodo]==1)return;
	if(upd[nodo]==-1)num--;
	if(num==0)ans++;
	
	for(auto i : adj[nodo]){
		if(i!=last){
			calc(i,nodo,num);
		}
	}	
}

int main(){

	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	
	vector<int> tmp;
	for(int i=0;i<=n;i++)adj.push_back(tmp);
	
	for(int i=1;i<=n;i++){
		cin>>val[i];
		opz[val[i]].push_back(i);
	}
	
	for(int i=0;i<n-1;i++){
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	preprocess(1);
	
	for(auto i : opz){
		
		tmp=i.second;
		if(tmp.size()==1)continue;
		
		int nod=-1;
		for(auto j : tmp){
			if(sub[j]!=0 && sub[j]!=conta[1][val[j]]-1){
				cout<<"0\n";
				return 0;
			}
			if(sub[j]==conta[1][val[j]]-1)nod=j;
		}
		
		int lc=-1;
		
		for(int j=0;j<tmp.size();j++){
			if(tmp[j]!=nod){
				if(lc==-1)lc=tmp[j];
				else lc=lca(tmp[j],lc);
				upd[tmp[j]]=1;
			}
		}
		
		if(lc==nod){
			cout<<0<<"\n";
			return 0;
		}
		
		if(nod==-1){
			for(auto j : tmp)upd[j]=1;
		}else{
			cont++;
			
			for(auto j : adj[nod]){
				if(lca(nod,j)==nod && lca(lc,j)==j){
					if(upd[j]!=1)
					upd[j]=-1;
					break;
				}
			}
		}
	}
	
	calc(1,1,cont);
	cout<<ans<<"\n";	

	return 0;
}
