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 = 200002;
const int MAXLOG = 22;


int N;
int ar[MAXN];
vector<int> G[MAXN];
int parent[MAXN], depth[MAXN], lca[MAXN][MAXLOG];
vector< pair<int, int> > sequence[MAXN];
int redDescendant[MAXN];
bool isRed[MAXN], isBlue[MAXN], invalid[MAXN];


void exitNo() {
	cout << "0\n";
	exit(0);
}


void input() {

	cin >> N;

	set<int> S;
	for (int i = 1 ; i <= N ; i++) {
		cin >> ar[i];
		S.insert(ar[i]);
	}	

	for (int i = 1 ; i <= N-1 ; i++) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}

	map<int, int> M;
	int cnt = 1;
	for (auto s : S) {
		M[s] = cnt;
		cnt++;
	}

	for (int i = 1 ; i <= N ; i++) {
		ar[i] = M[ar[i]];
	}
}


void DFS1(int at, int par, int d) {
	depth[at] = d;
	parent[at] = par;

	int val = ar[at];
	int prevCnt = sequence[val].back().first;
	sequence[val].push_back({prevCnt+1, at});

	for (int nxt : G[at]) {
		if (nxt != par) {
			DFS1(nxt, at, d+1);
		}
	}

	sequence[val].push_back({prevCnt, 0});
}


bool DFSRed(int at, int par) {
	bool seenRed = isRed[at];
	for (int nxt : G[at]) {
		if (nxt != par) {
			seenRed |= DFSRed(nxt, at);
			if (isRed[nxt] || redDescendant[nxt] > 0) {
				if (redDescendant[at] == 0) {
					redDescendant[at] = nxt;
				} else {
					exitNo();
				}
			}
		}
	}

	if (redDescendant[at] > 0) {
		for (int nxt : G[at]) {
			if (nxt != par && nxt != redDescendant[at]) {
				isBlue[nxt] = true;
			}
		}
	}

	if (seenRed) {
		invalid[at] = true;
	}

	return seenRed;
}


void DFSBlue(int at, int par, bool seenBlue) {
	seenBlue |= isBlue[at];

	if (seenBlue) {
		invalid[at] = true;
	}

	for (int nxt : G[at]) {
		if (nxt != par) {
			DFSBlue(nxt, at, seenBlue);
		}
	}
}


void prepareLCA() {
	for (int i = 1 ; i <= N ; i++) {
		lca[i][0] = parent[i];
	}

	for (int d = 1 ; d < MAXLOG ; d++) {
		for (int i = 1 ; i <= N ; i++) {
			lca[i][d] = lca[lca[i][d-1]][d-1];
		}
	}
}


int getAncestorAtDepth(int node, int ancestorDepth) {
	int diff = depth[node] - ancestorDepth;

	if (diff < 0) {
		cerr << "WTF\n";
		exit(0);
		return -1;
	}

	for (int d = 0 ; d < MAXLOG ; d++) {
		if (diff & (1<<d)) {
			node = lca[node][d];
		}
	}
	return node;
}


int getLCA(int u, int v) {
	if (depth[u] > depth[v]) {
		swap(u, v);
	}

	// cerr << "U = " << u << ", V = " << v << "\n";

	int diff = depth[v] - depth[u];

	// cerr << "Diff = " << diff << "\n";

	// for (int d = 0 ; d < MAXLOG ; d++) {
	// 	if (diff & (1<<d)) {
	// 		v = lca[v][d];
	// 	}
	// }

	v = getAncestorAtDepth(v, depth[u]);

	// cerr << "After height equivalence, U = " << u << ", V = " << v << "\n";

	if (u == v) {
		return u;
	}


	for (int d = MAXLOG-1 ; d >= 0 ; d--) {
		if (lca[u][d] != lca[v][d]) {
			u = lca[u][d];
			v = lca[v][d];
		}
	}
	// cerr << "During returning, U = " << u << ", V = " << v << "\n";

	return lca[u][0];
}



void checkIfImpossibleAndMark() {
	for (int i = 1 ; i <= N ; i++) {
		for (auto nxt : G[i]) {
			if (ar[i] == ar[nxt]) {
				exitNo();
			}
		}
	}

	for (int i = 1 ; i <= N ; i++) {
		int zero_f = 0, one_f = 0, two_f = 0, three_f = 0;
		if ((int)sequence[i].size() <= 3) {
			continue;
		}

		for (auto p : sequence[i]) {
			if (p.first == 0) {
				zero_f++;
			}
			if (p.first == 1) {
				one_f++;
			}
			if (p.first == 2) {
				two_f++;
			}
			if (p.first == 3) {
				three_f++;
			}
		}

		if (three_f > 0) {
			// cerr << "SAD three?\n";
			exitNo();
		}


		if (two_f > 0 && zero_f > 2) {
			// cerr << "SAD two?\n";
			exitNo();
		}

		if (two_f > 0) {
			int oneGuy = 0;
			for (auto p : sequence[i]) {
				if (p.first == 1 && p.second > 0) {
					oneGuy = p.second;
					isRed[oneGuy] = true;
				}
			}

			int correspondingChild = -1;
			// cerr << "Checking child now\n";

			for (auto p : sequence[i]) {
				if (p.first == 2 && p.second > 0) {
					isBlue[p.second] = true;

					int oneGuyChild = getAncestorAtDepth(p.second, depth[oneGuy]+1);
					// cerr << "oneGuyChild = " << oneGuyChild << "\n";
					if (correspondingChild == -1) {
						correspondingChild = oneGuyChild;
					} else {
						if (oneGuyChild != correspondingChild) {
							// cerr << "SAD\n";
							exitNo();
						}
					}
				}
			}

			for (auto nxt : G[oneGuy]) {
				if (nxt != parent[oneGuy] && nxt != correspondingChild) {
					isBlue[nxt] = true;
				}
			}
		} else {
			for (auto p : sequence[i]) {
				if (p.first == 1 && p.second > 0) {
					isBlue[p.second] = true;
				}
			}
		}
	}
}


void solve() {

	for (int i = 1 ; i <= N ; i++) {
		sequence[i].push_back({0, 0});
	}

	DFS1(1, 1, 0);

	prepareLCA();

	checkIfImpossibleAndMark();

	// for (int i = 1; i  <= N ; i++) {
	// 	cerr << "isRed[" << i << "] = " << isRed[i] << "\n";
	// }

	// for (int i = 1; i  <= N ; i++) {
	// 	cerr << "isBlue[" << i << "] = " << isBlue[i] << "\n";
	// }

	DFSRed(1, 1);
	DFSBlue(1, 1, false);

	int ans = 0;
	for (int i = 1 ; i <= N ; i++) {
		if (!invalid[i]) {
			ans++;
		}
	}

	cout << ans << "\n";
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cerr.tie(0);

	input();	
	solve();
}
