Problem: You have a rooted tree consisting of n vertices. Each vertex of the tree has some color. We will assume that the tree vertices are numbered by integers from 1 to n. Then we represent the color of vertex v as cv. The tree root is a vertex with number 1.

In this problem you need to answer to m queries. Each query is described by two integers vj, kj. The answer to query vj, kj is the number of such colors of vertices x, that the subtree of vertex vj contains at least kj vertices of color x.

You can find the definition of a rooted tree by the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory).

Input

The first line contains two integers n and m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105). The next line contains a sequence of integers c1, c2, ..., cn (1 ≤ ci ≤ 105). The next n - 1 lines contain the edges of the tree. The i-th line contains the numbers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — the vertices connected by an edge of the tree.

Next m lines contain the queries. The j-th line contains two integers vj, kj (1 ≤ vj ≤ n; 1 ≤ kj ≤ 105).

Output

Print m integers — the answers to the queries in the order the queries appear in the input.

Examples

Input

8 5
1 2 2 3 3 2 3 3
1 2
1 5
2 3
2 4
5 6
5 7
5 8
1 2
1 3
1 4
2 3
5 3


Output

2
2
1
0
1


Input

4 1
1 2 3 4
1 2
2 3
3 4
1 1


Output

4

Note

A subtree of vertex v in a rooted tree with root r is a set of vertices {u : dist(r, v) + dist(v, u) = dist(r, u)}. Where dist(x, y) is the length (in edges) of the shortest path between vertices x and y.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T& val) {
  std::fill((T*)array, (T*)(array + N), val);
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class _Key, class _Tp, class _Hash, bool DOWNSIZE>
class UnorderedMapIterator;
template <class _Key, class _Tp, class _Hash = hash<_Key>,
          bool DOWNSIZE = false>
class UnorderedMap {
 private:
  using iterator = UnorderedMapIterator<_Key, _Tp, _Hash, DOWNSIZE>;
  using value_type = _Tp;
  using data_type = pair<_Key, _Tp>;
  using aligned_pointer =
      typename aligned_storage<sizeof(value_type), alignof(value_type)>::type;
  friend UnorderedMapIterator<_Key, _Tp, _Hash, DOWNSIZE>;
  struct bucket {
    _Key _key;
    short int _dist;
    bool _last, _end;
    aligned_pointer _value_ptr;
    bucket() noexcept : _dist(-1), _last(false), _end(false) {}
    bucket& operator=(const bucket& another) noexcept {
      _key = another._key, _dist = another._dist, _last = another._last,
      _end = another._end;
      if (!another.empty()) {
        new (&_value_ptr) value_type(
            *reinterpret_cast<const value_type*>(&another._value_ptr));
      }
      return *this;
    }
    ~bucket() {
      if (!empty()) _delete();
    }
    inline void clear() noexcept { _dist = -1; }
    inline void _delete() { _dist = -1, value_ptr()->~value_type(); }
    inline bool empty() const noexcept { return (_dist == -1); }
    inline value_type& value() noexcept {
      return *reinterpret_cast<value_type*>(&_value_ptr);
    }
    inline value_type* value_ptr() noexcept {
      return reinterpret_cast<value_type*>(&_value_ptr);
    }
    inline void new_value(value_type&& value) {
      new (&_value_ptr) value_type(move(value));
    }
  };
  inline static unsigned int ceilpow2(unsigned int u) noexcept {
    if (u == 0u) return 0u;
    --u, u |= u >> 1, u |= u >> 2, u |= u >> 4, u |= u >> 8;
    return (u | (u >> 16)) + 1u;
  }
  inline static bucket* increment(bucket* cur) noexcept {
    for (++cur; !cur->_end; ++cur) {
      if (!cur->empty()) break;
    }
    return cur;
  }
  inline bucket* next_bucket(bucket* cur) const noexcept {
    return cur->_last ? _buckets : cur + 1;
  }
  inline unsigned int make_hash(const _Key& key) const noexcept {
    return _Hash()(key);
  }
  inline float load_rate() const noexcept {
    return (float)_data_count / _bucket_count;
  }
  bucket* insert(bucket* cur, _Key&& key, short int dist, value_type&& value) {
    bucket* ret = cur;
    bool flag = false;
    while (true) {
      if (cur->empty()) {
        cur->_key = move(key), cur->_dist = dist, cur->new_value(move(value));
        if (!flag) ret = cur, flag = true;
        break;
      } else if (dist > cur->_dist) {
        swap(key, cur->_key), swap(dist, cur->_dist), swap(value, cur->value());
        if (!flag) ret = cur, flag = true;
      }
      ++dist;
      cur = next_bucket(cur);
    }
    return ret;
  }
  template <class Key>
  bucket* _find(Key&& key, bool push = false) {
    unsigned int hash = make_hash(key);
    bucket* cur = _buckets + (hash & _mask);
    short int dist = 0;
    while (dist <= cur->_dist) {
      if (key == cur->_key) return cur;
      ++dist, cur = next_bucket(cur);
    }
    if (!push) return _buckets + _bucket_count;
    ++_data_count;
    if (rehash_check()) {
      cur = _buckets + (hash & _mask), dist = 0;
    }
    value_type new_value = value_type();
    _Key new_key = forward<Key>(key);
    return insert(cur, move(new_key), dist, move(new_value));
  }
  template <class Data>
  bucket* find_insert(Data&& data) {
    const _Key& key = data.first;
    unsigned int hash = make_hash(key);
    bucket* cur = _buckets + (hash & _mask);
    short int dist = 0;
    while (dist <= cur->_dist) {
      if (key == cur->_key) return cur;
      ++dist, cur = next_bucket(cur);
    }
    ++_data_count;
    if (rehash_check()) {
      cur = _buckets + (hash & _mask), dist = 0;
    }
    data_type new_data = forward<Data>(data);
    return insert(cur, move(new_data.first), dist, move(new_data.second));
  }
  template <typename... Args>
  bucket* emplace(Args&&... args) {
    return find_insert(data_type(forward<Args>(args)...));
  }
  bucket* backward_shift(bucket* cur, bool next_ret) {
    bucket *next = next_bucket(cur), *ret = cur;
    if (next->_dist < 1) return next_ret ? increment(cur) : cur;
    do {
      cur->_key = next->_key, cur->_dist = next->_dist - 1;
      cur->new_value(move(next->value()));
      cur = next, next = next_bucket(cur);
    } while (next->_dist >= 1);
    cur->clear();
    return ret;
  }
  bucket* erase_impl(bucket* cur, bool next_ret) {
    assert(static_cast<size_t>(cur - _buckets) != _bucket_count);
    cur->_delete();
    --_data_count;
    return backward_shift(cur, next_ret);
  }
  bucket* erase_itr(bucket* cur, bool next_ret = true) {
    const _Key key = cur->_key;
    return erase_impl(rehash_check() ? _find(key) : cur, next_ret);
  }
  size_t erase_key(const _Key& key) {
    rehash_check();
    bucket* cur = _find(key);
    if (static_cast<size_t>(cur - _buckets) == _bucket_count) {
      return 0;
    } else {
      erase_impl(_find(key), false);
      return 1;
    }
  }
  bool rehash_check() {
    if (_bucket_count == 0) {
      rehash(1u);
      return true;
    } else if (load_rate() >= MAX_LOAD_RATE) {
      rehash(_bucket_count * 2u);
      return true;
    } else if (DOWNSIZE) {
      if (load_rate() <= MIN_LOAD_RATE && _bucket_count >= DOWNSIZE_THRESHOLD) {
        rehash(_bucket_count / 2u);
        return true;
      }
    }
    return false;
  }
  void move_data(bucket* cur) {
    insert(_buckets + (make_hash(cur->_key) & _mask), move(cur->_key), 0,
           move(cur->value()));
  }
  void rehash(unsigned int new_bucket_count) {
    UnorderedMap new_unordered_map(new_bucket_count);
    new_unordered_map._data_count = _data_count;
    for (bucket* cur = _buckets; !cur->_end; ++cur) {
      if (!cur->empty()) {
        new_unordered_map.move_data(cur);
      }
    }
    swap(*this, new_unordered_map);
  }
  friend void swap(UnorderedMap& ump1, UnorderedMap& ump2) {
    swap(ump1._bucket_count, ump2._bucket_count);
    swap(ump1._mask, ump2._mask);
    swap(ump1._data_count, ump2._data_count);
    swap(ump1._buckets, ump2._buckets);
  }

 private:
  unsigned int _bucket_count, _mask, _data_count;
  bucket* _buckets;

 public:
  const float MAX_LOAD_RATE = 0.5f;
  const float MIN_LOAD_RATE = 0.1f;
  const unsigned int DOWNSIZE_THRESHOLD = 16u;
  UnorderedMap(unsigned int bucket_size = 0u)
      : _bucket_count(ceilpow2(bucket_size)),
        _mask(_bucket_count - 1),
        _data_count(0u),
        _buckets(new bucket[_bucket_count + 1]) {
    if (_bucket_count > 0)
      _buckets[_bucket_count - 1]._last = true;
    else
      _mask = 0;
    _buckets[_bucket_count]._end = true;
  }
  UnorderedMap(const UnorderedMap& another)
      : _bucket_count(another._bucket_count),
        _mask(another._mask),
        _data_count(another._data_count) {
    _buckets = new bucket[_bucket_count + 1u];
    for (unsigned int i = 0u; i <= _bucket_count; ++i) {
      _buckets[i] = another._buckets[i];
    }
  }
  UnorderedMap(UnorderedMap&& another)
      : _bucket_count(move(another._bucket_count)),
        _mask(move(another._mask)),
        _data_count(move(another._data_count)),
        _buckets(another._buckets) {
    another._buckets = nullptr;
  }
  UnorderedMap& operator=(const UnorderedMap& another) {
    delete[] _buckets;
    _bucket_count = another._bucket_count;
    _mask = another._mask;
    _data_count = another._data_count;
    _buckets = new bucket[_bucket_count + 1u];
    for (unsigned int i = 0u; i <= _bucket_count; ++i) {
      _buckets[i] = another._buckets[i];
    }
    return *this;
  }
  UnorderedMap& operator=(UnorderedMap&& another) {
    delete[] _buckets;
    _bucket_count = move(another._bucket_count);
    _mask = move(another._mask);
    _data_count = move(another._data_count);
    _buckets = another._buckets;
    another._buckets = nullptr;
    return *this;
  }
  void allocate(unsigned int element_size) {
    rehash(ceilpow2(ceil(element_size / MAX_LOAD_RATE) + 1));
  }
  ~UnorderedMap() { delete[] _buckets; }
  friend ostream& operator<<(ostream& os, UnorderedMap& ump) noexcept {
    for (auto val : ump) os << '{' << val.first << ',' << val.second << "} ";
    return os;
  }
  _Tp& operator[](const _Key& key) { return _find(key, true)->value(); }
  _Tp& operator[](_Key&& key) { return _find(move(key), true)->value(); }
  const _Tp& at(const _Key& key) {
    bucket* res = _find(key);
    if (res == _buckets + _bucket_count)
      __throw_out_of_range("Unordered_Map::at");
    return res->value();
  }
  void clear() {
    UnorderedMap new_unordered_map(0u);
    swap(*this, new_unordered_map);
  }
  size_t size() const noexcept { return _data_count; }
  size_t bucket_count() const noexcept { return _bucket_count; }
  bool empty() const noexcept { return (_data_count == 0); }
  iterator begin() noexcept {
    return (_buckets->empty() && _bucket_count > 0)
               ? iterator(increment(_buckets))
               : iterator(_buckets);
  }
  iterator end() noexcept { return iterator(_buckets + _bucket_count); }
  iterator find(const _Key& key) { return iterator(_find(key)); }
  iterator insert(const data_type& data) { return iterator(find_insert(data)); }
  iterator insert(data_type&& data) {
    return iterator(find_insert(move(data)));
  }
  template <typename... Args>
  iterator emplace(Args&&... args) {
    return iterator(_emplace(forward<Args>(args)...));
  }
  size_t erase(const _Key& key) { return erase_key(key); }
  iterator erase(const iterator& itr) {
    return iterator(erase_itr(itr.bucket_ptr));
  }
  void simple_erase(const _Key& key) { erase_key(key); }
  void simple_erase(const iterator& itr) { erase_itr(itr.bucket_ptr, false); }
  short int maximum_distance() const noexcept {
    short int ret = -1;
    for (bucket* cur = _buckets; !cur->_end; ++cur) {
      ret = max(ret, cur->_dist);
    }
    return ret;
  }
};
template <class _Key, class _Tp, class _Hash, bool DOWNSIZE>
class UnorderedMapIterator {
 private:
  friend UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>;
  typename UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>::bucket* bucket_ptr;
  using iterator_category = forward_iterator_tag;
  using value_type = pair<const _Key, _Tp>;
  using difference_type = ptrdiff_t;
  using reference = pair<const _Key&, _Tp&>;

 private:
  UnorderedMapIterator(
      typename UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>::bucket*
          _bucket_ptr) noexcept
      : bucket_ptr(_bucket_ptr) {}

 public:
  UnorderedMapIterator() noexcept : bucket_ptr() {}
  UnorderedMapIterator(const UnorderedMapIterator& itr) noexcept
      : bucket_ptr(itr.bucket_ptr) {}
  UnorderedMapIterator& operator=(const UnorderedMapIterator& itr) & noexcept {
    return bucket_ptr = itr.bucket_ptr, *this;
  }
  UnorderedMapIterator& operator=(const UnorderedMapIterator&& itr) & noexcept {
    return bucket_ptr = itr.bucket_ptr, *this;
  }
  reference operator*() const noexcept {
    return {bucket_ptr->_key, bucket_ptr->value()};
  }
  UnorderedMapIterator& operator++() noexcept {
    return bucket_ptr =
               UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>::increment(bucket_ptr),
           *this;
  }
  UnorderedMapIterator operator++(int) const noexcept {
    return UnorderedMapIterator(
        UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>::increment(this->bucket_ptr));
  }
  bool operator==(const UnorderedMapIterator& itr) const noexcept {
    return !(*this != itr);
  };
  bool operator!=(const UnorderedMapIterator& itr) const noexcept {
    return bucket_ptr != itr.bucket_ptr;
  }
};
template <typename T>
class RBST {
 private:
  struct node {
    T val;
    node *left, *right;
    int st_size;
    node() {}
    node(T v) : val(v), left(nullptr), right(nullptr), st_size(1) {}
    ~node() {
      delete left;
      delete right;
    }
  };
  node* root;
  using pnn = pair<node*, node*>;
  int size(node* t) { return t ? t->st_size : 0; }
  node* update(node* t) {
    node* l = t->left;
    node* r = t->right;
    t->st_size = size(l) + size(r) + 1;
    return t;
  }
  unsigned rnd() {
    static unsigned x = 123456789, y = 362436069, z = 521288629, w = 86675123;
    unsigned t = (x ^ (x << 11));
    x = y, y = z, z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
  }
  node* merge(node* l, node* r) {
    if (!l || !r) return (!l) ? r : l;
    if (rnd() % (size(l) + size(r)) < (unsigned)size(l)) {
      l->right = merge(l->right, r);
      return update(l);
    } else {
      r->left = merge(l, r->left);
      return update(r);
    }
  }
  pnn split(node* t, int k) {
    if (!t) return pnn(nullptr, nullptr);
    if (k <= size(t->left)) {
      pnn s = split(t->left, k);
      t->left = s.second;
      return pnn(s.first, update(t));
    } else {
      pnn s = split(t->right, k - size(t->left) - 1);
      t->right = s.first;
      return pnn(update(t), s.second);
    }
  }
  int lower_bound(node* t, const T k) {
    if (!t) return 0;
    if (t->val < k) {
      return size(t->left) + lower_bound(t->right, k) + 1;
    } else {
      return lower_bound(t->left, k);
    }
  }
  void lower_value(node* t, const T k, T& res) {
    if (!t) return;
    if (t->val < k) {
      lower_value(t->right, k, res);
    } else {
      lower_value(t->left, k, res = t->val);
    }
  }
  int upper_bound(node* t, const T k) {
    if (!t) return 0;
    if (t->val <= k) {
      return size(t->left) + upper_bound(t->right, k) + 1;
    } else {
      return upper_bound(t->left, k);
    }
  }
  void upper_value(node* t, const T k, T& res) {
    if (!t) return;
    if (t->val <= k) {
      upper_value(t->right, k, res);
    } else {
      upper_value(t->left, k, res = t->val);
    }
  }
  T get(node* t, int k) {
    if (!t) assert(false);
    int s = size(t->left);
    if (s > k)
      return get(t->left, k);
    else if (s < k)
      return get(t->right, k - s - 1);
    else
      return t->val;
  }
  node* insert(node* t, int k, node* u) {
    pnn s = split(t, k);
    return merge(merge(s.first, u), s.second);
  }
  pnn erase(node* t, int k) {
    pnn sr = split(t, k + 1);
    pnn sl = split(sr.first, k);
    return pnn(merge(sl.first, sr.second), sl.second);
  }

 public:
  RBST() : root(nullptr) {}
  int lower_bound(const T k) { return lower_bound(root, k); }
  T lower_value(const T k) {
    T res = numeric_limits<T>::max();
    lower_value(root, k, res);
    return res;
  }
  int upper_bound(const T k) { return upper_bound(root, k); }
  T upper_value(const T k) {
    T res = numeric_limits<T>::max();
    upper_value(root, k, res);
    return res;
  }
  void insert(T val) { root = insert(root, upper_bound(val), new node(val)); }
  void erase(T val) {
    node* p;
    tie(root, p) = erase(root, lower_bound(val));
    p->left = p->right = nullptr;
    delete p;
  }
  T get(int k) { return get(root, k); }
  void print() {
    int sz = size(root);
    for (int i = 0; i < (int)(sz); ++i) cout << get(i) << " ";
    cout << "\n";
  }
};
vector<RBST<pair<int, int> > > rbst;
vector<UnorderedMap<int, int> > mp;
int res[100010];
int c[100010];
vector<vector<int> > g;
vector<pair<int, int> > query[100010];
void dfs(int id, int pre) {
  int mx = -1;
  int t = -1;
  for (auto x : g[id]) {
    if (x == pre) continue;
    dfs(x, id);
    if (chmax(mx, (int)mp[x].size())) {
      t = x;
    }
  }
  if (t != -1) {
    swap(rbst[id], rbst[t]);
    swap(mp[id], mp[t]);
  }
  for (auto x : g[id]) {
    if (x == pre || x == t) continue;
    for (auto [val, cnt] : mp[x]) {
      if (mp[id].find(val) != mp[id].end()) {
        int C = mp[id][val];
        rbst[id].erase(make_pair(C, val));
        mp[id][val] += cnt;
        rbst[id].insert(make_pair(C + cnt, val));
      } else {
        mp[id][val] += cnt;
        rbst[id].insert(make_pair(cnt, val));
      }
    }
  }
  int val = c[id];
  int cnt = 1;
  if (mp[id].find(val) != mp[id].end()) {
    int C = mp[id][val];
    rbst[id].erase(make_pair(C, val));
    mp[id][val] += cnt;
    rbst[id].insert(make_pair(C + cnt, val));
  } else {
    mp[id][val] += cnt;
    rbst[id].insert(make_pair(cnt, val));
  }
  for (auto [cnt, qid] : query[id]) {
    res[qid] = (int)mp[id].size() - rbst[id].lower_bound(make_pair(cnt, -1));
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < (int)(n); ++i) cin >> c[i];
  g.resize(n);
  rbst.resize(n);
  mp.resize(n);
  for (int i = 0; i < (int)(n - 1); ++i) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 0; i < (int)(m); ++i) {
    int v, k;
    cin >> v >> k;
    v--;
    query[v].push_back(make_pair(k, i));
  }
  dfs(0, -1);
  for (int i = 0; i < (int)(m); ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}