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 <cassert>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <chrono>
#include <algorithm>
#include <numeric>
#include <atomic>
#include <tuple>
#include <fstream>
#include <random>
#include <future>
#include <iterator>
#include <functional>
#include <thread>
#include <bitset>
#include <cstddef>
#include <utility>
#include <type_traits>
#include <complex>
#include <array>
#include <map>
#include <set>
#include <deque>
#include <unordered_map>
#include <queue>

using namespace std;

const int MAXN = 2e5 + 10, MAXM = 40, MAXL = 20, ALP = 20, MOD = 1e9 + 7, MAXK = 17, INF = 1e9 + 10, MAXA = 1e2 + 10, MAXB = 24, MAXBB = (1 << MAXB);
const string  no = "NO\n", yes = "YES\n";
const int hA[4] = { 1, 0, -1, 0 }, kA[4] = { 0, 1, 0, -1 };


int64_t n, a[MAXN], cnt1[MAXN], cnt2[MAXN], mp[MAXN], mp1[MAXN], mp2[MAXN], all[MAXN];
vector<int> adj[MAXN];

int64_t dfs1(int c = 0, int p = -1) {
    int64_t ans = mp[a[c]];
    mp[a[c]]++;
    for (auto nxt : adj[c]) if (nxt != p) ans += dfs1(nxt, c);
    mp[a[c]]--;
    return ans;
}
void dfs_cnt(int c = 0, int p = -1) {
    int o1 = 0, o2 = 0;
    if (c) {
        o1 = mp1[a[p]];
        o2 = mp2[a[c]];
    }
    mp1[a[c]]++, mp2[a[c]]++;
    for (auto nxt : adj[c]) if (nxt != p) dfs_cnt(nxt, c);
    if (p != -1) {
        cnt1[c] = mp1[a[p]] - o1;
    }
    cnt2[c] = all[a[c]] - (mp2[a[c]] - o2);
    //mp1[a[c]] = o2 + 1;
}
int dfs2(int c, int p, int pv) {
    pv -= cnt1[c], pv += cnt2[c];
    int ans = (pv == 0);
    for (auto nxt : adj[c]) if (nxt != p) ans += dfs2(nxt, c, pv);
    return ans;
}
void solve() {
    //if my parent is bad, i can only be good if the only matches are from him into my subtree
    //if my parent is good, i can only be bad if i match from myself into his subtree
    cin >> n;
    unordered_map<int, int> enc(n);
    for (int i = 0, ptr = 0; i < n; i++) {
        cin >> a[i];
        if (enc.find(a[i]) == enc.end()) {
            enc[a[i]] = ptr;
            a[i] = ptr++;
        }
        else {
            a[i] = enc[a[i]];
        }
        ++all[a[i]];
    }
    for (int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b, --a, --b;
        adj[a].push_back(b), adj[b].push_back(a);
    }

    dfs_cnt();

    int v = dfs1();
    int ans = (v == 0);
    for (auto nxt : adj[0]) {
        ans += dfs2(nxt, 0, v);
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int t_c = 1;
    //cin >> t_c;
    while (t_c--) solve();
}