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;
typedef long long ll;

const int N = 2e5 + 200;
const int L = 18;
vector<int> g[N];
int tin[N], tout[N], timer, up[N][L + 1], a[N];
map<int, vector<int>> val;
bool can[N];

void dfs(int v, int p){
  tin[v] = ++timer;
  up[v][0] = p;
  for(int i = 1; i <= L; i ++)
    up[v][i] = up[up[v][i - 1]][i - 1];
  for(int to : g[v])
    if(to != p)
      dfs(to, v);
  tout[v] = ++timer;
}

bool upper(int a, int b){
  return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int get_lca(int a, int b){
  if(upper(a, b))
    return a;
  if(upper(b, a))
    return b;
  for(int i = L; i >= 0; i --)
    if(!upper(up[a][i], b))
      a = up[a][i];
  return up[a][0];
}

int sub[N];

void dfs2(int v, int p, int cur = 0){
  cur += sub[v];
  sub[v] = cur;
  for(int to : g[v])
    if(to != p)
      dfs2(to, v, cur);
}

int main(){
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int n; cin >> n;
  for(int i = 0; i < n; i ++){
    cin >> a[i];
    val[a[i]].push_back(i);
  }
  for(int i = 0; i < n - 1; i ++){
    int u, v;
    cin >> u >> v;
    u --; v --;
    g[v].push_back(u);
    g[u].push_back(v);
  }
  dfs(0, 0);
  int e = 0;
  for(auto [clr, b] : val){
    if(b.size() > 1){
      e ++;
      int lca = -1;
      for(int v : b){
        can[v] = false;
        if(lca == -1)
          lca = v;
        else
          lca = get_lca(lca, v);
      }
      sort(b.begin(), b.end(), [&](int a, int b){
              return tin[a] <= tin[b];
           });
      bool _lca = false, f = false;
      for(int x : b)
        if(x == lca)
          _lca = true;
      int cnt = 0;
      for(int i = 0; i + 1 < b.size(); i ++){
        if(tout[b[i]] >= tout[b[i + 1]])
          cnt ++;
        if(get_lca(b[i], b[i + 1]) == lca && b[i] != lca && b[i + 1] != lca)
          f = true;
      }
      if(cnt > 1 || ((_lca || cnt > 0) && f)){
        cout << 0;
        return 0;
      }
      if(_lca){
        for(int to : g[lca]){
          if(!upper(to, lca) && a[to] != clr){
            int l = 0, r = b.size();
            while(l < r){
              int mid = (l + r) / 2;
              if(tin[b[mid]] >= tin[to])
                r = mid;
              else
                l = mid + 1;
            }
            if(l < b.size() && tout[b[l]] <= tout[to])
              sub[to] ++;
          }
        }
        for(int x : b)
          if(x != lca)
            sub[x] --;
      }else{
        sub[0] ++;
        for(int x : b)
          sub[x] --;
      }
    }
  }
  dfs2(0, 0);
  int ans = 0;
  for(int i = 0; i < n; i ++)
    ans += (sub[i] == e);
  cout << ans;
}
