#include <bits/stdc++.h>
using namespace std;
const long long INFll = 1000000000000000000ll, INF = 0x3f3f3f3f,
                _MOD = (1000 * 1000 * 1000 + 7);
const long double EPS = 1e-8;
const long long* dolly = NULL;
const long long MAXN = 1000000 + 10;
class Nod {
 public:
  long long l, r, lz, val;
  Nod() { l = 0, r = 0, lz = 0, val = 0; }
};
long long n, segn, q, _a_variable_;
long long qArr[MAXN];
long long fn[MAXN], st[MAXN];
vector<long long> treeAdj[MAXN];
Nod nod[4 * MAXN];
vector<long long> qAdj[MAXN];
long long ans[MAXN];
void dfsStFn(long long v, long long p) {
  st[v] = _a_variable_++;
  for (long long u : treeAdj[v])
    if (u != p) dfsStFn(u, v);
  fn[v] = _a_variable_;
}
void make_tree() {
  for (long long i = 0; i < segn; i++) {
    nod[i + segn].l = i;
    nod[i + segn].r = i + 1;
  }
  for (long long i = segn - 1; i >= 1; i--) {
    nod[i].l = nod[(i << 1)].l;
    nod[i].r = nod[((i << 1) + 1)].r;
  }
}
void updateNodVal(long long pos) {
  nod[pos].val = nod[(pos << 1)].val + nod[((pos << 1) + 1)].val;
  if (nod[pos].lz) nod[pos].val = nod[pos].r - nod[pos].l;
}
void change(long long pos, long long l, long long r, bool b) {
  long long lpos = nod[pos].l;
  long long rpos = nod[pos].r;
  if (lpos >= r || rpos <= l) return;
  if (lpos >= l && rpos <= r) {
    b ? nod[pos].lz++ : nod[pos].lz--;
    if (b && nod[pos].lz == 1) nod[pos].val = nod[pos].r - nod[pos].l;
    if (!b && nod[pos].lz == 0) {
      if (pos >= segn)
        nod[pos].val = 0;
      else
        updateNodVal(pos);
    }
    return;
  }
  change((pos << 1), l, r, b);
  change(((pos << 1) + 1), l, r, b);
  updateNodVal(pos);
}
long long get() { return nod[1].val; }
void solveDfs(long long v, long long p) {
  if (qAdj[v].size()) change(1, st[v], fn[v], 1);
  for (long long u : qAdj[v]) {
    change(1, st[u], fn[u], 1);
  }
  ans[v] = get();
  for (long long u : treeAdj[v])
    if (u != p) {
      solveDfs(u, v);
    }
  if (qAdj[v].size()) change(1, st[v], fn[v], 0);
  for (long long u : qAdj[v]) change(1, st[u], fn[u], 0);
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  for (long long u, v, i = 0; i < n - 1; i++) {
    cin >> u >> v;
    treeAdj[--u].push_back(--v);
    treeAdj[v].push_back(u);
  }
  dfsStFn(0, 0);
  segn = pow(2, ceil(log2(n)));
  make_tree();
  for (long long u, v, i = 0; i < q; i++) {
    cin >> u >> v;
    qAdj[--u].push_back(--v);
    qAdj[v].push_back(u);
  }
  solveDfs(0, 0);
  for (long long i = 0; i < n; i++) cout << (ans[i] ? ans[i] - 1 : 0) << ' ';
  return cout << "\n", 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 INFll = 1000000000000000000ll, INF = 0x3f3f3f3f,
                _MOD = (1000 * 1000 * 1000 + 7);
const long double EPS = 1e-8;
const long long* dolly = NULL;
const long long MAXN = 1000000 + 10;
class Nod {
 public:
  long long l, r, lz, val;
  Nod() { l = 0, r = 0, lz = 0, val = 0; }
};
long long n, segn, q, _a_variable_;
long long qArr[MAXN];
long long fn[MAXN], st[MAXN];
vector<long long> treeAdj[MAXN];
Nod nod[4 * MAXN];
vector<long long> qAdj[MAXN];
long long ans[MAXN];
void dfsStFn(long long v, long long p) {
  st[v] = _a_variable_++;
  for (long long u : treeAdj[v])
    if (u != p) dfsStFn(u, v);
  fn[v] = _a_variable_;
}
void make_tree() {
  for (long long i = 0; i < segn; i++) {
    nod[i + segn].l = i;
    nod[i + segn].r = i + 1;
  }
  for (long long i = segn - 1; i >= 1; i--) {
    nod[i].l = nod[(i << 1)].l;
    nod[i].r = nod[((i << 1) + 1)].r;
  }
}
void updateNodVal(long long pos) {
  nod[pos].val = nod[(pos << 1)].val + nod[((pos << 1) + 1)].val;
  if (nod[pos].lz) nod[pos].val = nod[pos].r - nod[pos].l;
}
void change(long long pos, long long l, long long r, bool b) {
  long long lpos = nod[pos].l;
  long long rpos = nod[pos].r;
  if (lpos >= r || rpos <= l) return;
  if (lpos >= l && rpos <= r) {
    b ? nod[pos].lz++ : nod[pos].lz--;
    if (b && nod[pos].lz == 1) nod[pos].val = nod[pos].r - nod[pos].l;
    if (!b && nod[pos].lz == 0) {
      if (pos >= segn)
        nod[pos].val = 0;
      else
        updateNodVal(pos);
    }
    return;
  }
  change((pos << 1), l, r, b);
  change(((pos << 1) + 1), l, r, b);
  updateNodVal(pos);
}
long long get() { return nod[1].val; }
void solveDfs(long long v, long long p) {
  if (qAdj[v].size()) change(1, st[v], fn[v], 1);
  for (long long u : qAdj[v]) {
    change(1, st[u], fn[u], 1);
  }
  ans[v] = get();
  for (long long u : treeAdj[v])
    if (u != p) {
      solveDfs(u, v);
    }
  if (qAdj[v].size()) change(1, st[v], fn[v], 0);
  for (long long u : qAdj[v]) change(1, st[u], fn[u], 0);
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  for (long long u, v, i = 0; i < n - 1; i++) {
    cin >> u >> v;
    treeAdj[--u].push_back(--v);
    treeAdj[v].push_back(u);
  }
  dfsStFn(0, 0);
  segn = pow(2, ceil(log2(n)));
  make_tree();
  for (long long u, v, i = 0; i < q; i++) {
    cin >> u >> v;
    qAdj[--u].push_back(--v);
    qAdj[v].push_back(u);
  }
  solveDfs(0, 0);
  for (long long i = 0; i < n; i++) cout << (ans[i] ? ans[i] - 1 : 0) << ' ';
  return cout << "\n", 0;
}

```