#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 42;
int n, q;
struct info {
  int mini, times;
  int lazy;
};
info tree[nmax * 4];
pair<int, int> mrg(pair<int, int> ret, pair<int, int> a) {
  if (ret.first > a.first) {
    ret.first = a.first;
    ret.second = a.second;
  } else if (ret.first == a.first)
    ret.second += a.second;
  return ret;
}
pair<int, int> combine(info a, info b) {
  pair<int, int> ret = {1e9, 0};
  a.mini = a.mini + a.lazy;
  b.mini = b.mini + b.lazy;
  ret = mrg(ret, {a.mini, a.times});
  ret = mrg(ret, {b.mini, b.times});
  return ret;
}
void build(int node, int l, int r) {
  if (l == r) {
    tree[node].times = 1;
    return;
  }
  int av = (l + r) / 2;
  build(node * 2, l, av);
  build(node * 2 + 1, av + 1, r);
  tree[node].times = r - l + 1;
}
void push(int node) {
  if (tree[node].lazy) {
    tree[node * 2].lazy += tree[node].lazy;
    tree[node * 2 + 1].lazy += tree[node].lazy;
    pair<int, int> cmb = combine(tree[node * 2], tree[node * 2 + 1]);
    tree[node].mini = cmb.first;
    tree[node].times = cmb.second;
    tree[node].lazy = 0;
  }
}
void update(int node, int l, int r, int lq, int rq, int value) {
  if (l == lq && r == rq) {
    tree[node].lazy += value;
    return;
  }
  push(node);
  int av = (l + r) / 2;
  if (lq <= av) update(node * 2, l, av, lq, min(av, rq), value);
  if (av < rq) update(node * 2 + 1, av + 1, r, max(av + 1, lq), rq, value);
  pair<int, int> cmb = combine(tree[node * 2], tree[node * 2 + 1]);
  tree[node].mini = cmb.first;
  tree[node].times = cmb.second;
  tree[node].lazy = 0;
}
pair<int, int> query(int node, int l, int r, int lq, int rq) {
  if (l == lq && r == rq) {
    return {tree[node].mini + tree[node].lazy, tree[node].times};
  }
  push(node);
  int av = (l + r) / 2;
  pair<int, int> ret = {1e9, 0};
  if (lq <= av) ret = mrg(ret, query(node * 2, l, av, lq, min(av, rq)));
  if (av < rq)
    ret = mrg(ret, query(node * 2 + 1, av + 1, r, max(av + 1, lq), rq));
  return ret;
}
vector<int> adj[nmax];
int t;
int order[nmax], in[nmax], out[nmax];
void dfs(int node, int parent) {
  t++;
  in[node] = t;
  order[t] = node;
  for (auto k : adj[node])
    if (k != parent) dfs(k, node);
  out[node] = t;
}
pair<int, int> queries[nmax];
int output[nmax];
bool cover(int l, int r, pair<int, int> query) {
  int l_ = l;
  if (in[query.first] <= l_) l_ = max(l_, out[query.first]);
  if (in[query.second] <= l_) l_ = max(l_, out[query.second]);
  if (l_ >= r) {
    return 1;
  }
  l_ = l;
  if (in[query.second] <= l_) l_ = max(l_, out[query.second]);
  if (in[query.first] <= l_) l_ = max(l_, out[query.first]);
  if (l_ >= r) {
    return 1;
  }
  return 0;
}
bool common(int l, int r, pair<int, int> query) {
  if (max(l, in[query.first]) <= min(r, out[query.first])) return 1;
  if (max(l, in[query.second]) <= min(r, out[query.second])) return 1;
  return 0;
}
pair<int, int> meet(int l, int r, int k) {
  int a = max(l, in[k]);
  int b = min(r, out[k]);
  return {a, b};
}
vector<pair<pair<int, int>, int> > there[nmax];
void upd(int l, int r, int p, int q, int k1, int k2) {
  pair<int, int> where_ri = meet(p, q, k2);
  pair<int, int> where_le = meet(l, r, k1);
  if (where_ri.first <= where_ri.second && where_le.first <= where_le.second) {
    there[where_le.first].push_back({where_ri, 1});
    there[where_le.second + 1].push_back({where_ri, -1});
  }
}
vector<int> compress_active;
void run(int l, int r, int p, int q, vector<int> active) {
  for (auto k : active) {
    upd(l, r, p, q, queries[k].first, queries[k].first);
    upd(l, r, p, q, queries[k].first, queries[k].second);
    upd(l, r, p, q, queries[k].second, queries[k].first);
    upd(l, r, p, q, queries[k].second, queries[k].second);
  }
  for (int i = l; i <= r; i++) {
    for (auto k : there[i])
      update(1, 1, n, k.first.first, k.first.second, k.second);
    pair<int, int> ret = query(1, 1, n, p, q);
    if (ret.first == 0)
      output[order[i]] += (q - p + 1) - ret.second;
    else
      output[order[i]] += (q - p + 1);
  }
  for (int i = l; i <= r; i++) {
    for (auto k : there[i])
      update(1, 1, n, k.first.first, k.first.second, -k.second);
  }
  for (int i = l; i <= r + 1; i++) there[i].clear();
}
void my_merge(int l, int r, int p, int q, vector<int> active) {
  compress_active = {};
  for (auto k : active)
    if (common(l, r, queries[k]) && common(p, q, queries[k]))
      compress_active.push_back(k);
  active = compress_active;
  run(l, r, p, q, active);
  run(p, q, l, r, active);
}
void solve(int l, int r, vector<int> active) {
  if (l == r) return;
  for (auto k : active)
    if (cover(l, r, queries[k])) {
      for (int j = l; j <= r; j++) output[order[j]] += (r - l);
      return;
    }
  int av = (l + r) / 2;
  my_merge(l, av, av + 1, r, active);
  vector<int> le = {};
  for (auto k : active)
    if (common(l, av, queries[k])) le.push_back(k);
  solve(l, av, le);
  le = {};
  for (auto k : active)
    if (common(av + 1, r, queries[k])) le.push_back(k);
  solve(av + 1, r, le);
}
int main() {
  scanf("%i%i", &n, &q);
  build(1, 1, n);
  int u, v;
  for (int i = 1; i < n; i++) {
    scanf("%i%i", &u, &v);
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(1, 0);
  for (int i = 1; i <= q; i++) {
    cin >> queries[i].first >> queries[i].second;
    if (in[queries[i].first] > in[queries[i].second])
      swap(queries[i].first, queries[i].second);
  }
  vector<int> active = {};
  for (int i = 1; i <= q; i++) active.push_back(i);
  solve(1, n, active);
  for (int i = 1; i <= n; i++) printf("%i ", output[i]);
  printf("\n");
  return 0;
}

### Prompt

Create a solution in Cpp for the following problem:

The Little Elephant loves trees very much, he especially loves root trees.

He's got a tree consisting of n nodes (the nodes are numbered from 1 to n), with root at node number 1. Each node of the tree contains some list of numbers which initially is empty. 

The Little Elephant wants to apply m operations. On the i-th operation (1 ≤ i ≤ m) he first adds number i to lists of all nodes of a subtree with the root in node number ai, and then he adds number i to lists of all nodes of the subtree with root in node bi.

After applying all operations the Little Elephant wants to count for each node i number ci — the number of integers j (1 ≤ j ≤ n; j ≠ i), such that the lists of the i-th and the j-th nodes contain at least one common number.

Help the Little Elephant, count numbers ci for him.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 105) — the number of the tree nodes and the number of operations. 

Each of the following n - 1 lines contains two space-separated integers, ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi), that mean that there is an edge between nodes number ui and vi. 

Each of the following m lines contains two space-separated integers, ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), that stand for the indexes of the nodes in the i-th operation.

It is guaranteed that the given graph is an undirected tree.

Output

In a single line print n space-separated integers — c1, c2, ..., cn.

Examples

Input

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


Output

0 3 3 3 3 

Input

11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8


Output

0 6 7 6 0 2 0 5 4 5 5 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 42;
int n, q;
struct info {
  int mini, times;
  int lazy;
};
info tree[nmax * 4];
pair<int, int> mrg(pair<int, int> ret, pair<int, int> a) {
  if (ret.first > a.first) {
    ret.first = a.first;
    ret.second = a.second;
  } else if (ret.first == a.first)
    ret.second += a.second;
  return ret;
}
pair<int, int> combine(info a, info b) {
  pair<int, int> ret = {1e9, 0};
  a.mini = a.mini + a.lazy;
  b.mini = b.mini + b.lazy;
  ret = mrg(ret, {a.mini, a.times});
  ret = mrg(ret, {b.mini, b.times});
  return ret;
}
void build(int node, int l, int r) {
  if (l == r) {
    tree[node].times = 1;
    return;
  }
  int av = (l + r) / 2;
  build(node * 2, l, av);
  build(node * 2 + 1, av + 1, r);
  tree[node].times = r - l + 1;
}
void push(int node) {
  if (tree[node].lazy) {
    tree[node * 2].lazy += tree[node].lazy;
    tree[node * 2 + 1].lazy += tree[node].lazy;
    pair<int, int> cmb = combine(tree[node * 2], tree[node * 2 + 1]);
    tree[node].mini = cmb.first;
    tree[node].times = cmb.second;
    tree[node].lazy = 0;
  }
}
void update(int node, int l, int r, int lq, int rq, int value) {
  if (l == lq && r == rq) {
    tree[node].lazy += value;
    return;
  }
  push(node);
  int av = (l + r) / 2;
  if (lq <= av) update(node * 2, l, av, lq, min(av, rq), value);
  if (av < rq) update(node * 2 + 1, av + 1, r, max(av + 1, lq), rq, value);
  pair<int, int> cmb = combine(tree[node * 2], tree[node * 2 + 1]);
  tree[node].mini = cmb.first;
  tree[node].times = cmb.second;
  tree[node].lazy = 0;
}
pair<int, int> query(int node, int l, int r, int lq, int rq) {
  if (l == lq && r == rq) {
    return {tree[node].mini + tree[node].lazy, tree[node].times};
  }
  push(node);
  int av = (l + r) / 2;
  pair<int, int> ret = {1e9, 0};
  if (lq <= av) ret = mrg(ret, query(node * 2, l, av, lq, min(av, rq)));
  if (av < rq)
    ret = mrg(ret, query(node * 2 + 1, av + 1, r, max(av + 1, lq), rq));
  return ret;
}
vector<int> adj[nmax];
int t;
int order[nmax], in[nmax], out[nmax];
void dfs(int node, int parent) {
  t++;
  in[node] = t;
  order[t] = node;
  for (auto k : adj[node])
    if (k != parent) dfs(k, node);
  out[node] = t;
}
pair<int, int> queries[nmax];
int output[nmax];
bool cover(int l, int r, pair<int, int> query) {
  int l_ = l;
  if (in[query.first] <= l_) l_ = max(l_, out[query.first]);
  if (in[query.second] <= l_) l_ = max(l_, out[query.second]);
  if (l_ >= r) {
    return 1;
  }
  l_ = l;
  if (in[query.second] <= l_) l_ = max(l_, out[query.second]);
  if (in[query.first] <= l_) l_ = max(l_, out[query.first]);
  if (l_ >= r) {
    return 1;
  }
  return 0;
}
bool common(int l, int r, pair<int, int> query) {
  if (max(l, in[query.first]) <= min(r, out[query.first])) return 1;
  if (max(l, in[query.second]) <= min(r, out[query.second])) return 1;
  return 0;
}
pair<int, int> meet(int l, int r, int k) {
  int a = max(l, in[k]);
  int b = min(r, out[k]);
  return {a, b};
}
vector<pair<pair<int, int>, int> > there[nmax];
void upd(int l, int r, int p, int q, int k1, int k2) {
  pair<int, int> where_ri = meet(p, q, k2);
  pair<int, int> where_le = meet(l, r, k1);
  if (where_ri.first <= where_ri.second && where_le.first <= where_le.second) {
    there[where_le.first].push_back({where_ri, 1});
    there[where_le.second + 1].push_back({where_ri, -1});
  }
}
vector<int> compress_active;
void run(int l, int r, int p, int q, vector<int> active) {
  for (auto k : active) {
    upd(l, r, p, q, queries[k].first, queries[k].first);
    upd(l, r, p, q, queries[k].first, queries[k].second);
    upd(l, r, p, q, queries[k].second, queries[k].first);
    upd(l, r, p, q, queries[k].second, queries[k].second);
  }
  for (int i = l; i <= r; i++) {
    for (auto k : there[i])
      update(1, 1, n, k.first.first, k.first.second, k.second);
    pair<int, int> ret = query(1, 1, n, p, q);
    if (ret.first == 0)
      output[order[i]] += (q - p + 1) - ret.second;
    else
      output[order[i]] += (q - p + 1);
  }
  for (int i = l; i <= r; i++) {
    for (auto k : there[i])
      update(1, 1, n, k.first.first, k.first.second, -k.second);
  }
  for (int i = l; i <= r + 1; i++) there[i].clear();
}
void my_merge(int l, int r, int p, int q, vector<int> active) {
  compress_active = {};
  for (auto k : active)
    if (common(l, r, queries[k]) && common(p, q, queries[k]))
      compress_active.push_back(k);
  active = compress_active;
  run(l, r, p, q, active);
  run(p, q, l, r, active);
}
void solve(int l, int r, vector<int> active) {
  if (l == r) return;
  for (auto k : active)
    if (cover(l, r, queries[k])) {
      for (int j = l; j <= r; j++) output[order[j]] += (r - l);
      return;
    }
  int av = (l + r) / 2;
  my_merge(l, av, av + 1, r, active);
  vector<int> le = {};
  for (auto k : active)
    if (common(l, av, queries[k])) le.push_back(k);
  solve(l, av, le);
  le = {};
  for (auto k : active)
    if (common(av + 1, r, queries[k])) le.push_back(k);
  solve(av + 1, r, le);
}
int main() {
  scanf("%i%i", &n, &q);
  build(1, 1, n);
  int u, v;
  for (int i = 1; i < n; i++) {
    scanf("%i%i", &u, &v);
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(1, 0);
  for (int i = 1; i <= q; i++) {
    cin >> queries[i].first >> queries[i].second;
    if (in[queries[i].first] > in[queries[i].second])
      swap(queries[i].first, queries[i].second);
  }
  vector<int> active = {};
  for (int i = 1; i <= q; i++) active.push_back(i);
  solve(1, n, active);
  for (int i = 1; i <= n; i++) printf("%i ", output[i]);
  printf("\n");
  return 0;
}

```