#include <bits/stdc++.h>
using namespace std;
const int DIM = 100005;
int lef[DIM], rig[DIM], ans[DIM];
vector<int> edg[DIM], lst[DIM];
struct node {
  int lzy, mnm, cnt;
} sgt[DIM << 2];
void updl(int nd, int le, int ri) {
  if (le != ri) {
    sgt[nd << 1].lzy += sgt[nd].lzy;
    sgt[nd << 1 | 1].lzy += sgt[nd].lzy;
  }
  sgt[nd].mnm += sgt[nd].lzy;
  sgt[nd].lzy = 0;
}
node updn(node nl, node nr) {
  int mnm = min(nl.mnm, nr.mnm), cnt = 0;
  if (mnm == nl.mnm) cnt += nl.cnt;
  if (mnm == nr.mnm) cnt += nr.cnt;
  return {0, mnm, cnt};
}
void build(int nd, int le, int ri) {
  sgt[nd].cnt = ri - le + 1;
  if (le != ri) {
    int md = (le + ri) >> 1;
    build(nd << 1, le, md);
    build(nd << 1 | 1, md + 1, ri);
  }
}
void update(int nd, int le, int ri, int st, int en, int val) {
  if (st <= le and ri <= en) {
    sgt[nd].lzy += val;
    updl(nd, le, ri);
  } else {
    int md = (le + ri) >> 1;
    updl(nd << 1, le, md);
    updl(nd << 1 | 1, md + 1, ri);
    if (st <= md) update(nd << 1, le, md, st, en, val);
    if (en > md) update(nd << 1 | 1, md + 1, ri, st, en, val);
    sgt[nd] = updn(sgt[nd << 1], sgt[nd << 1 | 1]);
  }
}
void dfs1(int x, int f, int &pt) {
  lef[x] = ++pt;
  for (int y : edg[x])
    if (y != f) dfs1(y, x, pt);
  rig[x] = pt;
}
void dfs2(int x, int f, int n) {
  for (int y : lst[x]) {
    update(1, 1, n, lef[x], rig[x], +1);
    update(1, 1, n, lef[y], rig[y], +1);
  }
  if (sgt[1].mnm > 0)
    ans[x] = n;
  else
    ans[x] = n - sgt[1].cnt;
  for (int y : edg[x])
    if (y != f) dfs2(y, x, n);
  for (int y : lst[x]) {
    update(1, 1, n, lef[x], rig[x], -1);
    update(1, 1, n, lef[y], rig[y], -1);
  }
}
int main(void) {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    edg[x].push_back(y);
    edg[y].push_back(x);
  }
  int pt = 0;
  dfs1(1, 0, pt);
  build(1, 1, n);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    cin >> x >> y;
    lst[x].push_back(y);
    lst[y].push_back(x);
  }
  dfs2(1, 0, n);
  for (int i = 1; i <= n; ++i) cout << ans[i] - (ans[i] > 0) << " ";
  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>
using namespace std;
const int DIM = 100005;
int lef[DIM], rig[DIM], ans[DIM];
vector<int> edg[DIM], lst[DIM];
struct node {
  int lzy, mnm, cnt;
} sgt[DIM << 2];
void updl(int nd, int le, int ri) {
  if (le != ri) {
    sgt[nd << 1].lzy += sgt[nd].lzy;
    sgt[nd << 1 | 1].lzy += sgt[nd].lzy;
  }
  sgt[nd].mnm += sgt[nd].lzy;
  sgt[nd].lzy = 0;
}
node updn(node nl, node nr) {
  int mnm = min(nl.mnm, nr.mnm), cnt = 0;
  if (mnm == nl.mnm) cnt += nl.cnt;
  if (mnm == nr.mnm) cnt += nr.cnt;
  return {0, mnm, cnt};
}
void build(int nd, int le, int ri) {
  sgt[nd].cnt = ri - le + 1;
  if (le != ri) {
    int md = (le + ri) >> 1;
    build(nd << 1, le, md);
    build(nd << 1 | 1, md + 1, ri);
  }
}
void update(int nd, int le, int ri, int st, int en, int val) {
  if (st <= le and ri <= en) {
    sgt[nd].lzy += val;
    updl(nd, le, ri);
  } else {
    int md = (le + ri) >> 1;
    updl(nd << 1, le, md);
    updl(nd << 1 | 1, md + 1, ri);
    if (st <= md) update(nd << 1, le, md, st, en, val);
    if (en > md) update(nd << 1 | 1, md + 1, ri, st, en, val);
    sgt[nd] = updn(sgt[nd << 1], sgt[nd << 1 | 1]);
  }
}
void dfs1(int x, int f, int &pt) {
  lef[x] = ++pt;
  for (int y : edg[x])
    if (y != f) dfs1(y, x, pt);
  rig[x] = pt;
}
void dfs2(int x, int f, int n) {
  for (int y : lst[x]) {
    update(1, 1, n, lef[x], rig[x], +1);
    update(1, 1, n, lef[y], rig[y], +1);
  }
  if (sgt[1].mnm > 0)
    ans[x] = n;
  else
    ans[x] = n - sgt[1].cnt;
  for (int y : edg[x])
    if (y != f) dfs2(y, x, n);
  for (int y : lst[x]) {
    update(1, 1, n, lef[x], rig[x], -1);
    update(1, 1, n, lef[y], rig[y], -1);
  }
}
int main(void) {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    edg[x].push_back(y);
    edg[y].push_back(x);
  }
  int pt = 0;
  dfs1(1, 0, pt);
  build(1, 1, n);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    cin >> x >> y;
    lst[x].push_back(y);
    lst[y].push_back(x);
  }
  dfs2(1, 0, n);
  for (int i = 1; i <= n; ++i) cout << ans[i] - (ans[i] > 0) << " ";
  return 0;
}

```