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;

vector<int> e[200001], la[200001];
int ans, in[200001], out[200001], T, m, c[200001];
unordered_map<int, int> h;

bool flag;

void dfs(int x, int pre)
{
	in[x] = ++T;
	for (int nex : e[x])
	{
		if (nex != pre)
			dfs(nex, x);
	}
	out[x] = T;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		int x;
		scanf("%d", &x);
		if (!h.count(x))
			h[x] = ++m;
		la[h[x]].push_back(i);
	}
	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0);
	for (int i = 1; i <= m; i++)
	{
		if (la[i].size() == 1)
			continue;
		set<int> s;
		s.clear();
		for (int x : la[i])
			s.insert(in[x]);
		for (int x : la[i])
		{
			c[in[x]]++;
			c[in[x] + 1]--;
			int cnt = 0;
			if (s.lower_bound(in[x]) == s.begin() && s.lower_bound(out[x] + 1) == s.end())
				c[1]++, c[in[x]]--, c[out[x] + 1]++;
			else
				cnt++;
			for (int nex : e[x])
			{
				if (in[nex] > in[x])
				{
					auto it = s.lower_bound(in[nex]);
					if (it == s.end() || *it > out[nex])
						c[in[nex]]++, c[out[nex] + 1]--;
					else
						cnt++;
				}
			}
			if (cnt > 1)
			{
				puts("0");
				return 0;
			}
		}
	}
	int now = 0;
	for (int i = 1; i <= T; i++)
	{
		//printf("%d\n", c[i]);
		now += c[i];
		if (!now)
			ans++;
	}
	printf("%d", ans);
	return 0;
}