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 <iostream>
#include <cstdio>
#include <vector>
#include <map>

#define pb push_back
using namespace std;

const int N = 2e5+5;

int n, a[N], ans;
vector<int> ke[N], w[N];

map<int, int> top, cnt;
int pre[N], s[N], d[N], b[N];

void dfs1(int u, int p) {
    pre[u] = top[a[u]]; top[a[u]] = u;
    s[u] = 1; cnt[a[u]] += 1;

    for(int v: ke[u]) if (v!=p) {
        d[u] = 0; dfs1(v, u);

        w[u].pb(d[u]);
        s[u] += d[u];
        b[u] += b[v] > 0;
    } else w[u].pb(-1);
    b[u] += s[u] > 1;

    int v = top[a[u]] = pre[u];
    if (v) d[v] += s[u];
}
void dfs2(int u, int p, int bu) {
    int v, tmp, bv;
    for(int i=0; i<(int)ke[u].size(); ++i) {
        v = ke[u][i]; if (v == p) continue;

        tmp = bu - (cnt[a[u]] > 1) + (cnt[a[u]] - w[u][i] > 1) - (b[v] > 0);
        bv = b[v] - (s[v] > 1) + (cnt[a[v]] > 1) + tmp;

        dfs2(v, u, bv);
    }
    ans += bu == 0;
}
int main()
{
    ios::sync_with_stdio(); cin.tie(0);
    ///freopen("a.inp","r",stdin);

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

    dfs1(1, -1);
    dfs2(1, -1, b[1]);
    cout << ans << endl;
}
