#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 10, N = 1 << 18;
int n, m, in[MAXN], out[MAXN], rest[MAXN], cnt;
vector<int> g[MAXN], v[MAXN];
struct node {
  int mi, num, lazy;
} tree[N * 2];
void push_up(int index) {
  if (tree[index << 1].mi == tree[index << 1 | 1].mi) {
    tree[index].mi = tree[index << 1].mi;
    tree[index].num = tree[index << 1].num + tree[index << 1 | 1].num;
  } else {
    if (tree[index << 1].mi < tree[index << 1 | 1].mi) {
      tree[index] = tree[index << 1];
    } else {
      tree[index] = tree[index << 1 | 1];
    }
  }
}
void push_down(int index) {
  tree[index].mi += tree[index].lazy;
  if (index < N) {
    tree[index << 1].lazy += tree[index].lazy;
    tree[index << 1 | 1].lazy += tree[index].lazy;
  }
  tree[index].lazy = 0;
}
void add(int a, int b, int val = 1, int now = 1, int l = 1, int r = N + 1) {
  push_down(now);
  if (r <= a || l >= b) {
    return;
  }
  if (r <= b && l >= a) {
    tree[now].lazy += val;
    push_down(now);
    return;
  }
  int mid = (l + r) >> 1;
  add(a, b, val, now << 1, l, mid);
  add(a, b, val, now << 1 | 1, mid, r);
  push_up(now);
}
pair<int, int> query(int a, int b, int now = 1, int l = 1, int r = N + 1) {
  push_down(now);
  if (r <= a || l >= b) {
    return make_pair(INF, 0);
  }
  if (r <= b && l >= a) {
    return make_pair(tree[now].mi, tree[now].num);
  }
  int mid = (l + r) >> 1;
  pair<int, int> L, R;
  L = query(a, b, now << 1, l, mid);
  R = query(a, b, now << 1 | 1, mid, r);
  if (L.first != R.first) {
    return min(L, R);
  }
  L.second += R.second;
  return L;
}
void dfs(int now, int pre = 0) {
  in[now] = ++cnt;
  for (auto it : g[now]) {
    if (it != pre) {
      dfs(it, now);
    }
  }
  out[now] = ++cnt;
}
void go(int now, int pre = 0) {
  for (auto it : v[now]) {
    add(in[it], out[it] + 1);
  }
  for (auto it : g[now]) {
    if (it != pre) go(it, now);
  }
  pair<int, int> res = query(1, 2 * n + 1);
  if (res.first != 0) res.second = 0;
  rest[now] = (2 * n - res.second) / 2;
  for (auto it : v[now]) {
    add(in[it], out[it] + 1, -1);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 2 * N - 1; i >= 1; --i) {
    if (i >= N) {
      tree[i] = node{0, 1, 0};
    } else {
      tree[i] = node{0, tree[i << 1].num * 2, 0};
    }
  }
  dfs(1);
  for (int i = 1; i <= m; ++i) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[a].push_back(a);
    v[b].push_back(a);
    v[b].push_back(b);
  }
  go(1);
  for (int i = 1; i <= n; ++i) {
    cout << max(0, rest[i] - 1) << " ";
  }
  return 0;
}

### Prompt

Please formulate a Cpp solution to 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>
#pragma GCC optimize(2)
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 10, N = 1 << 18;
int n, m, in[MAXN], out[MAXN], rest[MAXN], cnt;
vector<int> g[MAXN], v[MAXN];
struct node {
  int mi, num, lazy;
} tree[N * 2];
void push_up(int index) {
  if (tree[index << 1].mi == tree[index << 1 | 1].mi) {
    tree[index].mi = tree[index << 1].mi;
    tree[index].num = tree[index << 1].num + tree[index << 1 | 1].num;
  } else {
    if (tree[index << 1].mi < tree[index << 1 | 1].mi) {
      tree[index] = tree[index << 1];
    } else {
      tree[index] = tree[index << 1 | 1];
    }
  }
}
void push_down(int index) {
  tree[index].mi += tree[index].lazy;
  if (index < N) {
    tree[index << 1].lazy += tree[index].lazy;
    tree[index << 1 | 1].lazy += tree[index].lazy;
  }
  tree[index].lazy = 0;
}
void add(int a, int b, int val = 1, int now = 1, int l = 1, int r = N + 1) {
  push_down(now);
  if (r <= a || l >= b) {
    return;
  }
  if (r <= b && l >= a) {
    tree[now].lazy += val;
    push_down(now);
    return;
  }
  int mid = (l + r) >> 1;
  add(a, b, val, now << 1, l, mid);
  add(a, b, val, now << 1 | 1, mid, r);
  push_up(now);
}
pair<int, int> query(int a, int b, int now = 1, int l = 1, int r = N + 1) {
  push_down(now);
  if (r <= a || l >= b) {
    return make_pair(INF, 0);
  }
  if (r <= b && l >= a) {
    return make_pair(tree[now].mi, tree[now].num);
  }
  int mid = (l + r) >> 1;
  pair<int, int> L, R;
  L = query(a, b, now << 1, l, mid);
  R = query(a, b, now << 1 | 1, mid, r);
  if (L.first != R.first) {
    return min(L, R);
  }
  L.second += R.second;
  return L;
}
void dfs(int now, int pre = 0) {
  in[now] = ++cnt;
  for (auto it : g[now]) {
    if (it != pre) {
      dfs(it, now);
    }
  }
  out[now] = ++cnt;
}
void go(int now, int pre = 0) {
  for (auto it : v[now]) {
    add(in[it], out[it] + 1);
  }
  for (auto it : g[now]) {
    if (it != pre) go(it, now);
  }
  pair<int, int> res = query(1, 2 * n + 1);
  if (res.first != 0) res.second = 0;
  rest[now] = (2 * n - res.second) / 2;
  for (auto it : v[now]) {
    add(in[it], out[it] + 1, -1);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 2 * N - 1; i >= 1; --i) {
    if (i >= N) {
      tree[i] = node{0, 1, 0};
    } else {
      tree[i] = node{0, tree[i << 1].num * 2, 0};
    }
  }
  dfs(1);
  for (int i = 1; i <= m; ++i) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[a].push_back(a);
    v[b].push_back(a);
    v[b].push_back(b);
  }
  go(1);
  for (int i = 1; i <= n; ++i) {
    cout << max(0, rest[i] - 1) << " ";
  }
  return 0;
}

```