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;

void fast () {
	ios::sync_with_stdio (0);
	cin.tie (0); cout.tie (0);
}
const int N = 200010;
int n, a[N], b[N], cnt, dd, L[N], R[N];
vector<int> g[N], adj[N];
bool down[N], up[N], ok[N];
int calc(vector<int>& pool, int l, int r) {
	return upper_bound (pool.begin(), pool.end(), r)
	 - upper_bound(pool.begin(), pool.end(), l - 1);
}
void dfs1(int u, int pre) {
	L[u] = ++dd;
	adj[a[u]].push_back(L[u]);
	
	for (auto v: g[u])
		if (v != pre) 
			dfs1(v, u);
	
	R[u] = dd; 
}
int S[N];
void dfs2(int u, int pre) {
	down[u] = (calc(adj[a[u]], L[u], R[u]) == 1);
	for (auto v: g[u])
		if (v != pre)
			dfs2(v, u), down[u] &= down[v], S[u] += (!down[v]);
}
void dfs3(int u, int pre) {
	int c = 0;
	for (int v: g[u])
		if (v != pre && calc (adj[a[u]], L[v], R[v])) c++;
	
	for (int v: g[u])
		if (v != pre) {
			if (calc (adj[a[u]], L[v], R[v])) --c;
			S[u] -= (!down[v]);
			up[v] = (up[u] && (!c) && (!S[u]) && (calc(adj[a[u]], L[u], R[u]) == adj[a[u]].size()));
			ok[v] = (up[v] && down[v]);
			ok[v] &= (adj[a[v]].size() == 1);
			if (calc (adj[a[u]], L[v], R[v])) ++c;
			S[u] += (!down[v]);
			dfs3(v, u);
		}
}
int main() {
	fast();
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i], b[++cnt] = a[i];
		
	sort (b + 1, b + cnt + 1);
	cnt = unique (b + 1, b + cnt + 1) - (b + 1);
	for (int i = 1; i <= n; ++i)
		a[i] = lower_bound (b + 1, b + cnt + 1, a[i]) - b;
		
	for (int i = 1, u, v; i < n; ++i) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	dfs1(1, 0);
	dfs2(1, 0);
	ok[1] = down[1];
	up[1] = 1;
	dfs3(1, 0);
//	cout << T << '\n';
//	for (int i = 1; i <= n; ++i)
//		cerr << i << ":" << ok[i] << '\n';
	cout << count (ok + 1, ok + n + 1, 1) << '\n';
	return 0;
}
