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 <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#define maxn 200005 
using namespace std;
int n, a[maxn], u, v, pr;
int cnt = 0, ans = 0, cf[maxn];
vector<int> G[maxn];
int fa[maxn][30], dep[maxn];
int vis[maxn];
map<int, int> p;
void dfs(int x, int fat)
{
	fa[x][0] = fat;
	dep[x] = dep[fat] + 1;
	for (int i = 1; i <= 23; i++)
	{
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
	}
	for (int i = 0; i < G[x].size(); i++)
	{
		int V = G[x][i];
		if(V == fat) continue;
		dfs(V, x);
	}
}
int LCA(int x, int y)
{
	if(dep[x] > dep[y]) swap(x, y);
	for (int i = 20; i >= 0; i--)
	{
		if(dep[fa[y][i]] > dep[x])
		{
			y = fa[y][i];
		}
	}
	return y;
}
int lca(int x, int y)
{
	if(dep[x] > dep[y]) swap(x, y);
	for (int i = 20; i >= 0; i--)
	{
		if(dep[fa[y][i]] >= dep[x])
		{
			y = fa[y][i];
		}
	}
	if(x == y) return x;
	for (int i = 20; i >= 0; i--)
	{
		if(fa[x][i] != fa[y][i])
		{
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}
void calc(int x, int fat, long long res)
{
	if(res < 0) return;
	int pl = res + cf[x];
	if(pl == cnt)
	{
		ans++;
		pr = x;
	}
	for (int i = 0; i < G[x].size(); i++)
	{
		int V = G[x][i];
		if(V == fat) continue;
		calc(V, x, pl);
	}
}
set<int> p2;
int check(int x, int fat)
{
	set<int>::iterator iter = p2.find (a[x]);
	if(iter != p2.end()) return 0;
	p2.insert(a[x]);
	for (int i = 0; i < G[x].size(); i++)
	{
		int V = G[x][i];
		if(V == fat) continue;
		if(!check(V, x)) return 0;
	}
	p2.erase(a[x]);
	return 1;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}
	for (int i = 1; i < n; i++)
	{
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1, 1);
	for (int i = 1; i <= n; i++)
	{
		map<int, int>::iterator iter = p.find(a[i]);
		if(iter != p.end())
		{
			int tmp = (iter->second);
			vis[i] = vis[tmp] = 1;
			int L = lca(i, tmp);
			if(L == i)
			{
				cf[LCA(i, tmp)]++;
				cf[tmp] -= n;
			}
			else if(L == tmp)
			{
				cf[LCA(i, tmp)]++;
				cf[i] -= n;
			}
			else
			{
				cf[1]++;
				cf[tmp] -= n;
				cf[i] -= n;
			}
			cnt++;
		}
		else p.insert(pair<int, int>(a[i], i));
	}
	calc(1, 1, 0);
	if(ans == 0)
	{
		printf("%d", ans);
		return 0;
	}
	if(check(pr, pr)) printf("%d", ans);
	else printf("0\n");
	return 0;
}