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;

// Problema E, div2 695

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define lli long long int
#define vi vector<int>
#define vlli vector<long long int>
#define pii pair<int, int>
#define plli pair<lli, lli>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repa(i, a, b) for(int i = (a); i >= (b); i--)
#define repv(x, v) for(auto x : v)
#define debug(x) cout << #x << " = " << x << endl
#define debugsl(x) cout << #x << " = " << x << ", "
#define debugarr(x, a, b) cout << #x << " = ["; rep(i, a, b) cout << x[i] << ", "; cout << "]\n"
#define pb push_back
#define nl "\n"

struct x{
    lli p;
    lli val;

    bool operator < (const x &a)
    const {
        return p < a.p;
    }
};

lli n,a,b,cont,res,act,raiz;
lli visitados[200002], hp[200002] ,euler[400002],arr[200002],ini[200002],fin[200002];
vector<lli> hijos[200002];
vector<x> intervalos;
unordered_map<lli,lli> pila,anteriores,frecuencia;

void DFS(lli pos) {

    visitados[pos] = 1;
    euler[cont] = pos;
    ini[pos] = cont++;

    for (auto h : hijos[pos])
        if (visitados[h] == 0) DFS(h);

    visitados[pos] = 0;
    euler[cont] = pos;
    fin[pos] = cont++;
}

void rangos(lli a,lli b,lli tipo) {

    if (tipo == 1) {

        intervalos.push_back({ini[a],+1});
        intervalos.push_back({fin[a]+1,-1});

        //especial
        intervalos.push_back({1,+1});
        intervalos.push_back({ini[b],-1});

        intervalos.push_back({fin[b]+1,+1});
        intervalos.push_back({cont,-1});

    }
    else {

        intervalos.push_back({ini[a],+1});
        intervalos.push_back({fin[a]+1,-1});

        intervalos.push_back({ini[b],+1});
        intervalos.push_back({fin[b]+1,-1});

    }

}

void R(lli pos) {

    if (pila.find(arr[pos]) != pila.end())
        rangos(pos, hp[ pila[arr[pos]] ],1);
    else {
        if (anteriores.find(arr[pos]) != anteriores.end()) rangos(pos,anteriores[arr[pos]],2);
        pila[arr[pos]] = pos;
        anteriores[arr[pos]] = pos;
    }

    visitados[pos] = 1;

    for (auto h : hijos[pos]) {
        hp[pos] = h;
        if (visitados[h] == 0) R(h);
    }
    hp[pos] = 0;

    if (pila.find(arr[pos]) != pila.end() && pila[ arr[pos] ] == pos) pila.erase(arr[pos]);
    visitados[pos] = 0;

}

int main()
{
    fastio;

    cin >> n;
    rep(i,1,n) {
        cin >> arr[i];
        frecuencia[ arr[i] ]++;
    }

    raiz = -1;
    rep(i,1,n) {
        if (frecuencia[arr[i]] == 1) {
            raiz = i;
            break;
        }
    }

    rep(i,1,n-1) {
        cin >> a >> b;
        hijos[a].push_back(b);
        hijos[b].push_back(a);
    }

    cont = 1;

    if (raiz == -1) cout << 0 << nl;
    else {
        DFS(raiz);

        R(raiz);

        sort(intervalos.begin(), intervalos.end());

        res = 0;
        a = 0;
        act = 0;
        rep(i,1,cont-1) {
            while (a < intervalos.size() && intervalos[a].p == i) {
                act += intervalos[a].val;
                a++;
            }

            if (act == 0 && visitados[ euler[i] ] == 0) {
                res++;
                visitados[euler[i]] = 1;
            }
        }

        cout << res;
    }

    return 0;
}
