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 <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <list>
#include <array>
#include <fstream>
typedef long long ll;
typedef long double ld;
using namespace std;

void bad()
{
    cout << "0\n";
    exit(0);
}
const int maxn = 2e5 + 79;
vector<int> et, tout(maxn), tin(maxn), ans(maxn, 0), a(maxn), dp(maxn, 0);
vector<vector<int> > g(maxn);
map<int, vector<int> > m;
void dfs(int v, int p)
{
    tin[v] = et.size();
    m[a[v]].push_back(tin[v]);
    et.push_back(v);
    for (int i : g[v])
        if (i != p)
        {
            dfs(i, v);
            et.push_back(v);
        }
    tout[v] = et.size() - 1;
}
int count_subtree(int v, int c) // spocita pocet kusov farby v podstrome vrcholu v
{
    return upper_bound(m[c].begin(), m[c].end(), tout[v]) - lower_bound(m[c].begin(), m[c].end(), tin[v]);
}
set<pair<int, int> > d; // pamatame si orientovane hrany
void dfs2(int v, int p)
{
    int e = -1;
    if (p != -1 && m[a[v]].size() - count_subtree(v, a[v])) e = p;
    for (int i : g[v])
    {
        if (i == p) continue;
        dfs2(i, v);
        dp[v] += dp[i];
        if (count_subtree(i, a[v]))
        {
            if (e != -1) bad();
            e = i;
        }
    }
    if (p != -1 && e == p) dp[p]++;
    if (e != -1) d.insert({ v, e });
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0, u, v; i < n - 1; i++)
    {
        cin >> u >> v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
    dfs(0, -1);
    dfs2(0, -1);
    if (dp[0] == d.size()) ans[0] = true;
    for (int i = 1; i < et.size(); i++) // ideme na rerooting
    {
        if (d.count({ et[i - 1], et[i] }) && d.count({ et[i], et[i - 1] })) bad();
        else if (d.count({ et[i - 1], et[i] }))
        {
            dp[et[i - 1]] -= dp[et[i]];
            dp[et[i]] += dp[et[i - 1]] + 1;
        }
        else if (d.count({ et[i], et[i - 1] }))
        {
            dp[et[i - 1]] -= dp[et[i]] + 1;
            dp[et[i]] += dp[et[i - 1]];
        }
        else
        {
            dp[et[i - 1]] -= dp[et[i]];
            dp[et[i]] += dp[et[i - 1]];
        }
        if (dp[et[i]] == d.size()) ans[et[i]] = true;
    }
    cout << count(ans.begin(), ans.end(), 1) << "\n";
    return 0;
}