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;
const int MAXN = 3e5 + 5;
typedef long long ll;
map<ll, int> num;
map<ll, int> sum;
ll col[MAXN];
ll col_fa[MAXN];
ll a[MAXN];
ll f[MAXN];
ll g[MAXN];
vector<int> adj[MAXN];
int n;
ll ans;
void dfs1(int u, int fa) {
	sum[a[u]]++;
	col[u] = -sum[a[u]];
	if(fa) col_fa[u] = -sum[a[fa]];
	for(int i : adj[u]) if(i != fa) {
		dfs1(i, u);
		f[u] += f[i];
	}
	col[u] += sum[a[u]];
	f[u] += col[u];
	if(fa) {
		col_fa[u] += sum[a[fa]];
	}
}
void dfs2(int u, int fa) {
	if(fa) {
		g[u] = g[fa] + num[a[u]] - col[u] - 1;
		g[u] += f[fa] - f[u] - col_fa[u];
	} else {
		g[u] = 0;
	}
	for(int i : adj[u]) if(i != fa) {
		dfs2(i, u);
	}
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		num[a[i]]++;
	}
	for(int i = 1; i < n; i++) {
		int f, t;
		scanf("%d%d", &f, &t);
		adj[f].push_back(t);
		adj[t].push_back(f);
	}
	dfs1(1, 0);
	dfs2(1, 0);
	for(int i = 1; i <= n ; i++) if(f[i] + g[i] == 0) ans++;
	printf("%lld",ans);
	return 0;
}
