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>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <unordered_map>
#include <queue>
#include <map>
#include <sstream>
#include <set>
#include <cstdlib>
#include <ctime>
#include <unordered_set>
#include <bitset>
#include <fstream>
#include <chrono>
using namespace std;
typedef long long ll;
#pragma GCC optimize(3, "Ofast", "inline")
#define fir(i, a, b) for (int i = a; i <= b; i++)
#define mov(i) (1ll << i)
#define MAX_INF 0x3f3f3f3f
const int mod = 1e9 + 7;
struct ios
{
    inline char read()
    {
        static const int IN_LEN = 1e6 + 10;
        static char buf[IN_LEN], *s, *t;
        return (s == t) && (t = (s = buf) + fread(buf, 1, IN_LEN, stdin)), s == t ? -1 : *s++;
    }
    template <typename _Tp>
    inline ios &operator>>(_Tp &x)
    {
        static char c11, boo;
        for (c11 = read(), boo = 0; !isdigit(c11); c11 = read())
        {
            if (c11 == -1)
                return *this;
            boo |= c11 == '-';
        }
        for (x = 0; isdigit(c11); c11 = read())
            x = x * 10 + (c11 ^ '0');
        boo && (x = -x);
        return *this;
    }
} io;
namespace IO
{
    template <typename T>
    inline void w(T x)
    {
        if (x > 9)
            w(x / 10);
        putchar(x % 10 + 48);
    }
    template <typename T>
    inline void write(T x, char c)
    {
        if (x < 0)
            putchar('-'), x = -x;
        w(x);
        putchar(c);
    }
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        T f = 1;
        char c = getchar();
        for (; !isdigit(c); c = getchar())
            if (c == '-')
                f = -1;
        for (; isdigit(c); c = getchar())
            x = (x << 1) + (x << 3) + (c ^ 48);
        x *= f;
    }
} // namespace IO
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
ll qpow(ll a, ll b, ll p)
{

    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
void input()
{
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
}
const int maxn = 2e5 + 10;
int w[maxn];
vector<int> a[maxn];
int f[maxn];
map<int,int> mp,now;
void dfs(int u,int fa)
{
    int cur=now[w[u]];
    now[w[u]]++;
    for(auto v:a[u])
    {
        if(v!=fa)
        {
            int curson=now[w[u]];
            dfs(v,u);
            if(curson!=now[w[u]])
            {
                f[1]++,f[v]--;
            }
        }
    }
    int num=now[w[u]]-cur;
    if(num!=mp[w[u]])
    f[u]++;
}
void get(int u,int fa)
{
    for(auto v:a[u])
    {
        if(v!=fa)
        {
            f[v]+=f[u];
            get(v,u);
        }
    }
}
int main()
{
   // input();
    int n;
    cin>>n;
    fir(i,1,n)
    {
        scanf("%d",&w[i]);
        if(!mp.count(w[i]))mp[w[i]]=0;
        mp[w[i]]++;
        now[w[i]]=0;
    }
    fir(i,2,n)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(1,0);
    get(1,0);
    int ans=0;
    //fir(i,1,n)
    //cout<<i<<':'<<f[i]<<endl;
    fir(i,1,n)
    ans+=(f[i]==0?1:0);
    cout<<ans<<endl;
}