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;
       
       
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
       
//#define GCC optimize("O3, Ofast")
//#define GCC optimize("unroll-loops")
#define aidar asadulin
        
#define int long long
#define ull long long
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define pip pair<int, pii>
#define fi first
#define se second
#define all(_v) _v.begin(), _v.end()
#define sz(a) (int) (a.size())
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)
#define ld double
       
const int inf = 2e9 + 7;
const int max_n = 2e5 + 3;

int n;
int a[max_n];
vector<int> gr[max_n];
bool dp1[max_n], dp2[max_n];
map<int, int> cnt;
map<int, int> b[max_n];

void dfs(int v, int pr) {
	for(int to : gr[v]) {
		if (to == pr) continue;
		dfs(to, v);
		if (b[to][a[v]] != 0) dp2[to] = true;
		if (sz(b[v]) < sz(b[to])) swap(b[v], b[to]);
		for(auto i : b[to]) 
			b[v][i.fi] += i.se;
	}

	b[v][a[v]]++;

	if (cnt[a[v]] > b[v][a[v]]) dp1[v] = true;
	//if (b[v][a[v]] != 1) dp2[v] = true; 
}

void dfs1(int v, int pr) {
	for(int to : gr[v]) {
		if (to == pr) continue;
		if (dp1[v]) dp1[to] = true;
		dfs1(to, v);
		if (dp2[to]) dp2[v] = true;
	}
}

void dfs2(int v, int pr) {
	bool ba = false;
	for(int to : gr[v]) {
		if (to != pr) {
			if (dp2[to]) ba = true;
		}
	}
	if (!ba) dp2[v] = false;

	int c = 0;
	for(int to : gr[v]) {
		if (to != pr && dp2[to]) {
			for(int to1 : gr[v]) {
				if (to1 == to || to1 == pr) continue;
				dp1[to1] = true;
			}
		}
	}

	for(int to : gr[v]) {
		if (to != pr) {
			if (dp1[v]) dp1[to] = true;
			dfs2(to, v);
		}
	}
}

void solve() {
	cin >> n;

	for(int i = 0;i < n;i++) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	for(int i = 0;i < n - 1;i++) {
		int v1, v2;
		cin >> v1 >> v2;
		v1--; v2--;
		gr[v1].emplace_back(v2);
		gr[v2].emplace_back(v1);
	}

	dfs(0, -1);
	//for(int i = 0;i < n;i++)
	//	cout << dp1[i] << " " << dp2[i] << endl;

	dfs1(0, -1);
	dfs2(0, -1);
	int res = 0;
	for(int i = 0;i < n;i++) 
		if (!dp1[i] && !dp2[i]) res++;
	cout << res << endl;
}


signed main() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    cout.precision(10);

    solve();
}
	  	    			  	     	  	 							