#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int n, n2 = 1, m, st[100010], ed[100010], dat[10000000], ls[10000000],
       rs[10000000], ans[100010], len;
vector<int> g[100010], v[100010];
void dfs(int pos, int no) {
  st[pos] = len++;
  for (int i = 0; i < g[pos].size(); i++)
    if (g[pos][i] != no) dfs(g[pos][i], pos);
  ed[pos] = len - 1;
}
void build(int k, int lb, int ub) {
  len = max(len, k);
  if (lb == ub) return;
  ls[k] = k * 2 + 1;
  rs[k] = k * 2 + 2;
  build(ls[k], lb, (lb + ub) / 2);
  build(rs[k], (lb + ub) / 2 + 1, ub);
}
int upd(int k, int lb, int ub, int tlb, int tub) {
  if (ub < tlb || tub < lb || dat[k] == ub - lb + 1) return k;
  int kk = ++len;
  dat[kk] = dat[k];
  if (tlb <= lb && ub <= tub) {
    dat[kk] = ub - lb + 1;
    return kk;
  }
  ls[kk] = upd(ls[k], lb, (lb + ub) / 2, tlb, tub);
  rs[kk] = upd(rs[k], (lb + ub) / 2 + 1, ub, tlb, tub);
  dat[kk] = dat[ls[kk]] + dat[rs[kk]];
  return kk;
}
void dfs2(int pos, int no, int root) {
  for (int i = 0; i < v[pos].size(); i++) {
    root = upd(root, 0, n2 - 1, st[v[pos][i]], ed[v[pos][i]]);
  }
  ans[pos] = dat[root] - (dat[root] > 0 ? 1 : 0);
  for (int i = 0; i < g[pos].size(); i++)
    if (g[pos][i] != no) dfs2(g[pos][i], pos, root);
}
int main() {
  cin >> n >> m;
  int x, y;
  for (int i = 0; i < n - 1; i++) {
    scanf("%d%d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &x, &y);
    v[x].push_back(x);
    v[x].push_back(y);
    v[y].push_back(x);
    v[y].push_back(y);
  }
  for (int i = 1; i <= n; i++) {
    sort(v[i].begin(), v[i].end());
    v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
  }
  dfs(1, 0);
  while (n2 < n) n2 *= 2;
  for (int i = 0; i < 9999995; i++) ls[i] = rs[i] = -1;
  len = 0;
  build(0, 0, n2 - 1);
  dfs2(1, 0, 0);
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  cout << endl;
  return 0;
}

### Prompt

Generate 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>
using namespace std;
const long long MOD = 1e9 + 7;
int n, n2 = 1, m, st[100010], ed[100010], dat[10000000], ls[10000000],
       rs[10000000], ans[100010], len;
vector<int> g[100010], v[100010];
void dfs(int pos, int no) {
  st[pos] = len++;
  for (int i = 0; i < g[pos].size(); i++)
    if (g[pos][i] != no) dfs(g[pos][i], pos);
  ed[pos] = len - 1;
}
void build(int k, int lb, int ub) {
  len = max(len, k);
  if (lb == ub) return;
  ls[k] = k * 2 + 1;
  rs[k] = k * 2 + 2;
  build(ls[k], lb, (lb + ub) / 2);
  build(rs[k], (lb + ub) / 2 + 1, ub);
}
int upd(int k, int lb, int ub, int tlb, int tub) {
  if (ub < tlb || tub < lb || dat[k] == ub - lb + 1) return k;
  int kk = ++len;
  dat[kk] = dat[k];
  if (tlb <= lb && ub <= tub) {
    dat[kk] = ub - lb + 1;
    return kk;
  }
  ls[kk] = upd(ls[k], lb, (lb + ub) / 2, tlb, tub);
  rs[kk] = upd(rs[k], (lb + ub) / 2 + 1, ub, tlb, tub);
  dat[kk] = dat[ls[kk]] + dat[rs[kk]];
  return kk;
}
void dfs2(int pos, int no, int root) {
  for (int i = 0; i < v[pos].size(); i++) {
    root = upd(root, 0, n2 - 1, st[v[pos][i]], ed[v[pos][i]]);
  }
  ans[pos] = dat[root] - (dat[root] > 0 ? 1 : 0);
  for (int i = 0; i < g[pos].size(); i++)
    if (g[pos][i] != no) dfs2(g[pos][i], pos, root);
}
int main() {
  cin >> n >> m;
  int x, y;
  for (int i = 0; i < n - 1; i++) {
    scanf("%d%d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &x, &y);
    v[x].push_back(x);
    v[x].push_back(y);
    v[y].push_back(x);
    v[y].push_back(y);
  }
  for (int i = 1; i <= n; i++) {
    sort(v[i].begin(), v[i].end());
    v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
  }
  dfs(1, 0);
  while (n2 < n) n2 *= 2;
  for (int i = 0; i < 9999995; i++) ls[i] = rs[i] = -1;
  len = 0;
  build(0, 0, n2 - 1);
  dfs2(1, 0, 0);
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  cout << endl;
  return 0;
}

```