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;
#define N 200005
#define For(i,x,y)for(i=x;i<=(y);i++)
struct node
{
	int next,to;
}e[400005];
map<int,int>col;
bool vis[N],fa[N],son[N];
int a[N],head[N],sta[N],last[N],pos[N],g,cnt,top;
int read()
{
	int A;
	bool K;
	char C;
	C=A=K=0;
	while(C<'0'||C>'9')K|=C=='-',C=getchar();
	while(C>'/'&&C<':')A=(A<<3)+(A<<1)+(C^48),C=getchar();
	return(K?-A:A);
}
inline void add(int u,int v)
{
	e[++g].to=v;
	e[g].next=head[u];
	head[u]=g;
}
void dfs(int u,int t)
{
	int i,v,tmp;
	vis[u]=1;
	sta[++top]=u;
	pos[u]=top;
	if(!col.count(a[u]))tmp=col[a[u]]=++cnt;
	else
	{
		tmp=col[a[u]];
		if(vis[last[tmp]])fa[sta[pos[last[tmp]]+1]]=1;
		else son[last[tmp]]=1;
		son[u]=1;
	}
	last[tmp]=u;
	for(i=head[u];i;i=e[i].next)
	{
		v=e[i].to;
		if(v==t)continue;
		dfs(v,u);
		last[tmp]=u;
	}
	vis[u]=0;
	top--;
}
pair<int,int>calc(int u,int t)
{
	int i,v,tot,siz;
	pair<int,bool>pa;
	tot=siz=0;
	for(i=head[u];i;i=e[i].next)
	{
		v=e[i].to;
		if(v==t)continue;
		pa=calc(v,u);
		/*cout<<v<<' '<<pa.first<<' '<<pa.second<<endl;*/
		siz+=pa.second;
		if(siz>1)cout<<0,exit(0);
		if(!siz)tot+=pa.first;
		else if(pa.second)tot=pa.first;
	}
	return make_pair((son[u]?0:tot+(!siz)),siz||fa[u]);
}
int main()
{
	int n,i,u,v;
	n=read();
	For(i,1,n)a[i]=read();
	For(i,1,n-1)
	{
		u=read(),v=read();
		add(u,v),add(v,u);
	}
	dfs(1,0);
	/*For(i,1,n)cout<<son[i]<<' '<<fa[i]<<endl;*/
	cout<<calc(1,0).first;
	return 0;
}