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 int long long 


const int N = 2000002;

vector <int> adj[N];

int st[N], en[N], t, a[N], s[N];

map <int, int> mp[N], c;


void add(int l, int r, int x) {
    s[l] += x;
    s[r + 1] -= x;
}

void dfs(int v, int p) {
    st[v] = ++t;
    for(int u: adj[v]) if(u ^ p) {
        dfs(u, v);
    }
    en[v] = t;
}

void DFS(int v, int p) {
    for(int u: adj[v]) if(p ^ u) {
        DFS(u, v);
        if(mp[u].find(a[v]) != mp[u].end()) {
            add(1, t, +1);
            add(st[u], en[u], -1);
        }
        if(mp[v].size() < mp[u].size()) swap(mp[v], mp[u]);
    }
    for(int u: adj[v]) if(p ^ u) {
        for(auto &[x, c]: mp[u]) {
            mp[v][x] += c;
        }
    }
    ++mp[v][a[v]];
    if(mp[v][a[v]] < c[a[v]]) {
        add(st[v], en[v], +1);
    }
}

int32_t main() {
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        ++c[a[i]];
    }

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

    dfs(1, 0);
    DFS(1, 0);
    

    int ans = 0;

    for(int i = 1; i <= t; i++) {
        s[i] += s[i - 1];
        ans += !s[i];
    }

    cout << ans << endl;
}