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>

#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef vector<ll> dlist;
typedef vector<dlist> matrix;

void solve(){
    int n, a, b;
    cin >> n;
    vector<int> data(n);
    for(auto &x:data) cin >> x;
    data.insert(data.begin(), 0);

    matrix ady(n + 1);
    for(int i = 1; i < n; ++i){
        cin >> a >> b;
        ady[a].push_back(b);
        ady[b].push_back(a);
    }

    auto answer = [](int v){
        cout << v << "\n";
        exit(0);
    };

    int cant = 0;
    set<int> numbers;
    map<int, int> pos;
    vector<bool> non_valid(n + 1);

    function<void(int, int, int)> check = [&](int v, int dad, int b){
        if(numbers.count(data[v])) answer(0);
        b += non_valid[v];
        cant += !b;
        numbers.insert(data[v]);
        for(auto &x:ady[v]){
            if(x != dad)
                check(x, v, b);
        }
        numbers.erase(data[v]);
        b -= non_valid[v];
    };

    function<void(int, int)> marker = [&](int v, int dad){
        non_valid[pos[data[v]]] = non_valid[v] = true;
        pos[data[v]] = v;
        for(auto &x:ady[v]){
            if(x != dad)
                marker(x, v);
        }
    };

    function<void(int, int)> visitor = [&](int v, int dad){
        if(pos.count(data[v])){
            marker(v, dad);
            return;
        }
        pos[data[v]] = v;
        for(auto &x:ady[v]){
            if(x != dad){
                visitor(x, v);
                if(non_valid[v]){
                    marker(v, x);
                    if(non_valid[x]) answer(0);
                    else check(x, -1, 0);
                    answer(cant);
                }
            }
        }
    };

    visitor(1, -1);
    check(1, -1, 0);
    answer(cant);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    while(t--) solve();

    return 0;
}//RUL0