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.
import java.util.*;
import java.io.*;

public class CFA {
  BufferedReader br;
  PrintWriter out;
  StringTokenizer st;
  boolean eof;
  private static final long MOD = 1000L * 1000L * 1000L + 7;
  private static final int[] dx = {0, -1, 0, 1};
  private static final int[] dy = {1, 0, -1, 0};
  private static final String yes = "Yes";
  private static final String no = "No";

  void solve() {
//    int T = nextInt();
    int T = 1;
    for (int i = 0; i < T; i++) {
      helper();
    }
  }


  int n;
  int[] arr;
  List<List<Integer>> graph;
  int[] delta;
  int[] par;
  void helper() {
    n = nextInt();
    arr = nextIntArr(n);
    graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      graph.add(new ArrayList<>());
    }
    for (int i = 0; i < n - 1; i++) {
      int from = nextInt() - 1;
      int to = nextInt() - 1;
      graph.get(from).add(to);
      graph.get(to).add(from);
    }
    int[] startIndex = new int[n];
    int[] endIndex = new int[n];
    par = new int[n];
    dfs(-1, 0, startIndex, endIndex);
    Map<Integer, List<Integer>> val2Time = new HashMap<>();
    Map<Integer, Integer> hist = new HashMap<>();
    for (int i = 0; i < n; i++) {
      if (!val2Time.containsKey(arr[i])) {
        val2Time.put(arr[i], new ArrayList<>());
      }
      val2Time.get(arr[i]).add(startIndex[i]);
      hist.put(arr[i], hist.getOrDefault(arr[i], 0) + 1);
    }
    for (List<Integer> ls : val2Time.values()) {
      Collections.sort(ls);
    }

    int LIMIT = 2 * 100 * 1000 + 10;
    delta = new int[LIMIT];
    int[] directed = new int[n];
    Arrays.fill(directed, -1);
    for (int i = 0; i < n; i++) {
      List<Integer> seq = val2Time.get(arr[i]);
      if (seq.size() <= 1) {
        continue;
      }
      int cnt = 0;
      int directedTo = -1;
      int numInChildren = 0;
      for (int nxt : graph.get(i)) {
        if (nxt == par[i]) {
          continue;
        }
        // Search [startIndex[nxt], endIndex[nxt]].
        int num = searchNumber(seq, startIndex[nxt], endIndex[nxt]);
        if (num >= 1) {
          directedTo = nxt;
          numInChildren += num;
          cnt++;
        }
      }

      int numInParent = hist.get(arr[i]) - 1 - numInChildren;
      if (numInParent > 0) {
        cnt++;
      }
      directed[i] = directedTo == -1 ? par[i] : directedTo;
      if (cnt >= 2) {
        outln(0);
        return;
      }
    }
    int[] degree = new int[n];
    for (int i = 0; i < n; i++) {
      if (directed[i] == -1) {
        continue;
      }
      degree[directed[i]]++;
    }
    Deque<Integer> deck = new LinkedList<>();
    List<Integer> top = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      if (degree[i] == 0) {
        deck.add(i);
      }
    }
    while (!deck.isEmpty()) {
      int cur = deck.pollFirst();
      top.add(cur);
      int nxt = directed[cur];
      if (nxt == -1) {
        continue;
      }
      degree[nxt]--;
      if (degree[nxt] == 0) {
        deck.add(nxt);
      }
    }

    for (int v : degree) {
      if (v != 0) {
        outln(0);
        return;
      }
    }
    boolean[] black = new boolean[n];
    for (int v : top) {
      if (directed[v] == -1) {
        continue;
      }

      dfs(directed[v], v, black);
    }
    int res = 0;
    for (boolean b : black) {
      if (!b) {
        res++;
      }
    }
    outln(res);
  }

  // Search how many numbers in seq, which is [startVal, endVal].
  int searchNumber(List<Integer> seq, int startVal, int endVal) {
    int low = 0;
    int high = seq.size();
    while (low < high) {
      int mid = (low + high) / 2;
      int comp = seq.get(mid).compareTo(startVal);
      if (comp < 0) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }

    if (low == seq.size()) {
      return 0;
    }
    int first = low;
    low = 0;
    high = seq.size();
    while (low < high) {
      int mid = (low + high) / 2;
      int comp = seq.get(mid).compareTo(endVal);
      if (comp <= 0) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    int second = low - 1;
    return second - first + 1;
  }

  void dfs(int par, int cur, boolean[] black) {
    if (black[cur]) {
      return;
    }
    black[cur] = true;
    for (int nxt : graph.get(cur)) {
      if (nxt == par) {
        continue;
      }
      dfs(cur, nxt, black);
    }
  }

  // Euler's tour:
  int INDEX = 0;
  void dfs(int parent, int nodeIndex, int[] startIndex, int[] endIndex) {
    startIndex[nodeIndex] = INDEX;
    INDEX++;
    par[nodeIndex] = parent;
    for (int nxt : graph.get(nodeIndex)) {
      if (nxt != parent) {
        dfs(nodeIndex, nxt, startIndex, endIndex);
      }
    }
    endIndex[nodeIndex] = INDEX - 1;
  }

  void shuffle(long[] a) {
    int n = a.length;
    for(int i = 0; i < n; i++) {
      int r = i + (int) (Math.random() * (n - i));
      long tmp = a[i];
      a[i] = a[r];
      a[r] = tmp;
    }
  }

  long gcd(long a, long b) {
    while(a != 0 && b != 0) {
      long c = b;
      b = a % b;
      a = c;
    }
    return a + b;
  }
  private void outln(Object o) {
    out.println(o);
  }
  private void out(Object o) {
    out.print(o);
  }
  private void formatPrint(double val) {
    outln(String.format("%.9f%n", val));
  }
  public CFA() {
    br = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(System.out);
    solve();
    out.close();
  }
  public static void main(String[] args) {
    new CFA();
  }

  public long[] nextLongArr(int n) {
    long[] res = new long[n];
    for(int i = 0; i < n; i++)
      res[i] = nextLong();
    return res;
  }
  public int[] nextIntArr(int n) {
    int[] res = new int[n];
    for(int i = 0; i < n; i++)
      res[i] = nextInt();
    return res;
  }
  public String nextToken() {
    while (st == null || !st.hasMoreTokens()) {
      try {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e) {
        eof = true;
        return null;
      }
    }
    return st.nextToken();
  }
  public String nextString() {
    try {
      return br.readLine();
    } catch (IOException e) {
      eof = true;
      return null;
    }
  }
  public int nextInt() {
    return Integer.parseInt(nextToken());
  }
  public long nextLong() {
    return Long.parseLong(nextToken());
  }
  public double nextDouble() {
    return Double.parseDouble(nextToken());
  }
}