#include <bits/stdc++.h>
using namespace std;
const int N = 100123;
const int inf = 1e9 + 2;
int z, n, m, a, b;
int pre[N];
int post[N];
int par[N];
int val[N];
int add[N];
int sum[N];
int ans[N];
int T;
vector<int> nbs[N];
vector<int> qs[N];
vector<int> buckets;
bool inter(int a, int b, int p, int q) { return max(a, p) <= min(b, q); }
void update(int b, int le, int ri, int v) {
  int s = buckets[b];
  int e = buckets[b + 1] - 1;
  assert(le >= s);
  assert(ri <= e);
  for (int i = s; i <= e; i++) {
    val[i] += add[b];
  }
  add[b] = 0;
  for (int i = le; i <= ri; i++) {
    val[i] += v;
    assert(val[i] >= 0);
  }
  int mn = inf;
  for (int i = s; i <= e; i++) {
    mn = min(mn, val[i]);
  }
  add[b] = mn;
  sum[b] = e - s + 1;
  for (int i = s; i <= e; i++) {
    val[i] -= mn;
    if (!val[i]) sum[b]--;
    assert(val[i] >= 0);
  }
}
void change_range(int le, int ri, int v) {
  vector<int> affected;
  for (int i = 0; i < (int)buckets.size() - 1; i++) {
    int b = buckets[i];
    int nb = buckets[i + 1];
    if (inter(b, nb - 1, le, ri)) affected.push_back(i);
  }
  assert(affected.size());
  if (affected.size() <= 1) {
    update(affected[0], le, ri, v);
  } else {
    for (int i = 1; i < (int)affected.size() - 1; i++) {
      add[affected[i]] += v;
      assert(add[affected[i]] >= 0);
    }
    update(affected.front(), le, buckets[affected[1]] - 1, v);
    update(affected.back(), buckets[affected.back()], ri, v);
  }
}
void add_v(int v) { change_range(pre[v], post[v], 1); }
void remove_v(int v) { change_range(pre[v], post[v], -1); }
int get_sum(int b, int v) {
  int s = buckets[b];
  int e = buckets[b + 1] - 1;
  int res = 0;
  if (add[b]) {
    res += e - s + 1;
    if (pre[v] >= s && pre[v] <= e) res--;
  } else if (pre[v] >= s && pre[v] <= e) {
    for (int i = s; i <= e; i++) res += (i != pre[v] && val[i]);
  } else
    res += sum[b];
  return res;
}
void dfs1(int v, int p) {
  pre[v] = ++T;
  par[v] = p;
  for (int w : nbs[v])
    if (w != p) {
      dfs1(w, v);
    }
  post[v] = T;
}
void dfs2(int v, int p) {
  for (int q : qs[v]) {
    add_v(q);
  }
  if (qs[v].size()) add_v(v);
  int cans = 0;
  for (int b = 0; b < (int)buckets.size() - 1; b++) {
    cans += get_sum(b, v);
  }
  ans[v] = cans;
  for (int w : nbs[v])
    if (w != p) {
      dfs2(w, v);
    }
  for (int q : qs[v]) {
    remove_v(q);
  }
  if (qs[v].size()) remove_v(v);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 0; i < (int)n - 1; i++) {
    cin >> a >> b;
    nbs[a].push_back(b);
    nbs[b].push_back(a);
  }
  dfs1(1, 0);
  for (int i = 0; i < (int)m; i++) {
    cin >> a >> b;
    qs[a].push_back(b);
    qs[b].push_back(a);
  }
  buckets.push_back(1);
  int sq = sqrt(n);
  int cur = sq;
  while (cur < n) {
    buckets.push_back(cur);
    cur += sq;
  }
  buckets.push_back(n + 1);
  dfs2(1, 0);
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
  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 N = 100123;
const int inf = 1e9 + 2;
int z, n, m, a, b;
int pre[N];
int post[N];
int par[N];
int val[N];
int add[N];
int sum[N];
int ans[N];
int T;
vector<int> nbs[N];
vector<int> qs[N];
vector<int> buckets;
bool inter(int a, int b, int p, int q) { return max(a, p) <= min(b, q); }
void update(int b, int le, int ri, int v) {
  int s = buckets[b];
  int e = buckets[b + 1] - 1;
  assert(le >= s);
  assert(ri <= e);
  for (int i = s; i <= e; i++) {
    val[i] += add[b];
  }
  add[b] = 0;
  for (int i = le; i <= ri; i++) {
    val[i] += v;
    assert(val[i] >= 0);
  }
  int mn = inf;
  for (int i = s; i <= e; i++) {
    mn = min(mn, val[i]);
  }
  add[b] = mn;
  sum[b] = e - s + 1;
  for (int i = s; i <= e; i++) {
    val[i] -= mn;
    if (!val[i]) sum[b]--;
    assert(val[i] >= 0);
  }
}
void change_range(int le, int ri, int v) {
  vector<int> affected;
  for (int i = 0; i < (int)buckets.size() - 1; i++) {
    int b = buckets[i];
    int nb = buckets[i + 1];
    if (inter(b, nb - 1, le, ri)) affected.push_back(i);
  }
  assert(affected.size());
  if (affected.size() <= 1) {
    update(affected[0], le, ri, v);
  } else {
    for (int i = 1; i < (int)affected.size() - 1; i++) {
      add[affected[i]] += v;
      assert(add[affected[i]] >= 0);
    }
    update(affected.front(), le, buckets[affected[1]] - 1, v);
    update(affected.back(), buckets[affected.back()], ri, v);
  }
}
void add_v(int v) { change_range(pre[v], post[v], 1); }
void remove_v(int v) { change_range(pre[v], post[v], -1); }
int get_sum(int b, int v) {
  int s = buckets[b];
  int e = buckets[b + 1] - 1;
  int res = 0;
  if (add[b]) {
    res += e - s + 1;
    if (pre[v] >= s && pre[v] <= e) res--;
  } else if (pre[v] >= s && pre[v] <= e) {
    for (int i = s; i <= e; i++) res += (i != pre[v] && val[i]);
  } else
    res += sum[b];
  return res;
}
void dfs1(int v, int p) {
  pre[v] = ++T;
  par[v] = p;
  for (int w : nbs[v])
    if (w != p) {
      dfs1(w, v);
    }
  post[v] = T;
}
void dfs2(int v, int p) {
  for (int q : qs[v]) {
    add_v(q);
  }
  if (qs[v].size()) add_v(v);
  int cans = 0;
  for (int b = 0; b < (int)buckets.size() - 1; b++) {
    cans += get_sum(b, v);
  }
  ans[v] = cans;
  for (int w : nbs[v])
    if (w != p) {
      dfs2(w, v);
    }
  for (int q : qs[v]) {
    remove_v(q);
  }
  if (qs[v].size()) remove_v(v);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 0; i < (int)n - 1; i++) {
    cin >> a >> b;
    nbs[a].push_back(b);
    nbs[b].push_back(a);
  }
  dfs1(1, 0);
  for (int i = 0; i < (int)m; i++) {
    cin >> a >> b;
    qs[a].push_back(b);
    qs[b].push_back(a);
  }
  buckets.push_back(1);
  int sq = sqrt(n);
  int cur = sq;
  while (cur < n) {
    buckets.push_back(cur);
    cur += sq;
  }
  buckets.push_back(n + 1);
  dfs2(1, 0);
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
  return 0;
}

```