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.
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>		//UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>		//do setprecision
#include <ctime>
#include <complex>
#include <chrono>
#include<unordered_map>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define ALL(u) (u).begin(),(u).end()

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define LL long long
#define ULL unsigned LL
#define LD long double

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef tuple<int, int, int> TIII;
typedef vector<int> VI;

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;

void fast_io() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

const int MR = 2e5 + 10;

vector<int> g[MR];

bool done[MR];

int a[MR];

map<int, int> M;

multiset<int> S[MR];
int wsk[MR], subTreeColorCnt[MR];

// lista bezposrednich synow, ktorzy sprawiaja, ze dany wierzcholek nie ma distinct sciezki
vector<int> bad[MR];

void dfs1(int nr)
{
    done[nr] = 1;

    // polacz zbiory i zobacz, czy w poddrzewie jest dana wartosc
    S[nr].insert(a[nr]);
    wsk[nr] = nr;

    for (int i : g[nr])
        if (!done[i])
        {
            dfs1(i);
            // jesli dziecko nie moze byc korzeniem dla poddrzewa lub zawiera kolor ojca
            // odznacz, ze rodzic ma z nim problem
            if (!bad[i].empty() || S[wsk[i]].count(a[nr]))
                bad[nr].push_back(i);

            // lacz zbiory
            if (S[wsk[nr]].size() < S[wsk[i]].size())
                swap(wsk[nr], wsk[i]);

            while (!S[wsk[i]].empty())
            {
                auto it = S[wsk[i]].begin();
                S[wsk[nr]].insert(*it);
                S[wsk[i]].erase(it);
            }
        }

    // to nam do drugiego dfs-a sie przyda, zeby zobaczyc, czy ojciec tez sprawia problem
    subTreeColorCnt[nr] = S[wsk[nr]].count(a[nr]);
    M[a[nr]]++;
}

void dfs2(int nr, int par)
{
    done[nr] = 0;

    // zobacz, czy rodzic sprawia problem
    if (par != -1)
    {
        // czy ma min 1 syna sprawiajacego problem roznego od nr

        if (!bad[par].empty() && (bad[par].size() > 1 || bad[par].front() != nr))
            bad[nr].push_back(par);
        // lub czy ma kolor syna w poddrzewie roznym od niego
        else if (subTreeColorCnt[nr] != M[a[nr]])
            bad[nr].push_back(par);
    }

    for (int i : g[nr])
        if (done[i])
            dfs2(i, nr);
}

int main()
{
    fast_io();
    int n;
    scanf("%d", &n);
    REP(i, n)
        scanf("%d", &a[i]);

    REP(i, n - 1)
    {
        int u, v;
        scanf("%d%d", &u, &v); u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs1(0);
    dfs2(0, -1);

    int res = 0;
    REP(i, n)
        res += bad[i].empty();

    printf("%d\n", res);

    return 0;
}

// FOR GNU C++ use the following pattern:
// Uncomment the code below and change your main into main2
// It does not build in MS C++
// But it does increase the stack size from 256 MB on CF and uses GNU C++

//#include <Processthreadsapi.h>
//#include <iostream>
//#include <Synchapi.h>
//#include <windows.h>
//#include <process.h>
//
//DWORD WINAPI MyThreadFunction(LPVOID lpParam) {
//    main2(nullptr);
//    return 0;
//}
//int main() {
//    auto h = CreateThread(nullptr, 1024 << 20, MyThreadFunction, nullptr, STACK_SIZE_PARAM_IS_A_RESERVATION, nullptr);
//    WaitForSingleObject(h, INFINITE);
//}