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;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

int main(){ _

	int n; cin >> n;
	vector<int> a(n);
	for(int& i : a) cin >> i;
	
	auto oa = a;
	sort(oa.begin(), oa.end());
	auto it = unique(oa.begin(), oa.end());
	oa.resize(distance(oa.begin(), it));
	map<int,int> mp;
	int m = oa.size();
	for(int i = 0; i < m; i++) mp[oa[i]] = i;
	for(auto& i : a) i = mp[i];

	vector<vector<int>> ct(m);
	for(int i = 0; i < n; i++) ct[a[i]].push_back(i);

	vector<vector<int>> g(n);
	for(int i = 0; i < n-1; i++) {
		int u, v; cin >> u >> v; u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	int time = 0;
	vector<int> in(n,-1), out(n);
	function<void(int)> tour = [&] (int v) {
		in[v] = time;
		for(auto u : g[v]) if(in[u] == -1) tour(u);
		out[v] = time++;
	};

	tour(0);

	auto very_bad = [&] () {
		cout << 0 << endl;
		exit(0);
	};

	vector<int> sum(n+1, 0);
	auto update = [&] (int l, int r, int x) {
		sum[l] += x, sum[r + 1] -= x;
	};

	for(int i = 0; i < m; i++) if(ct[i].size() > 1) {
		vector<pair<int,int>> aux;
		for(auto u : ct[i]) aux.push_back({out[u], u});
		sort(aux.begin(), aux.end());

		set<int> cur;
		int anc = -1, nanc = 0;
		for(auto [outt, u] : aux) {
			int l = in[u], r = out[u];
			if(nanc and r > out[anc]) very_bad();
			
			auto itl = cur.lower_bound(l);
			auto itr = cur.upper_bound(r);
			
			if(itl != itr) {
				anc = u, nanc++;
				if(itl != cur.begin() or itr != cur.end()) very_bad();
			}
			if(nanc > 2) very_bad();
			
			cur.insert(r);
		}

		if(nanc == 0) {
			for(auto u : ct[i]) update(in[u], out[u], 1);
		}
		else {
			bool found = false;
			int good_child = -1;
			for(auto u : g[anc]) if(out[u] < out[anc]) {
				int l = in[u], r = out[u];
				auto itl = cur.lower_bound(l);
				auto itr = cur.upper_bound(r);

				if(itl != itr) {
					if(found) very_bad();
					found = true;
					good_child = u;
				}
			}

			update(0, n-1, 1);
			update(in[good_child], out[good_child], -1);
			for(auto u : ct[i]) if(u != anc) {
				update(in[u], out[u], 1);
			}
		}
	}

	int ans = 0;
	for(int i = 0; i < n; i++) {
		if(i) sum[i] += sum[i-1];
		if(!sum[i]) {
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}