#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <class T>
inline T max1(T a, T b) {
  return a > b ? a : b;
}
template <class T>
inline T min1(T a, T b) {
  return a < b ? a : b;
}
template <class T>
inline T gcd1(T a, T b) {
  if (a < b) swap(a, b);
  if (a % b == 0) return b;
  return gcd1(b, a % b);
}
template <class T>
inline T lb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned long long nValue) {
  nValue = ((0xaaaaaaaaaaaaaaaaull & nValue) >> 1) +
           (0x5555555555555555ull & nValue);
  nValue = ((0xccccccccccccccccull & nValue) >> 2) +
           (0x3333333333333333ull & nValue);
  nValue = ((0xf0f0f0f0f0f0f0f0ull & nValue) >> 4) +
           (0x0f0f0f0f0f0f0f0full & nValue);
  nValue = ((0xff00ff00ff00ff00ull & nValue) >> 8) +
           (0x00ff00ff00ff00ffull & nValue);
  nValue = ((0xffff0000ffff0000ull & nValue) >> 16) +
           (0x0000ffff0000ffffull & nValue);
  nValue = ((0xffffffff00000000ull & nValue) >> 32) +
           (0x00000000ffffffffull & nValue);
  return nValue;
}
inline int jud(double a, double b) {
  if (abs1(a - b) < eps) return 0;
  if (a < b) return -1;
  return 1;
}
long long pow(long long n, long long m, long long mod = 0) {
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
const int maxn = 101000;
int n, nq;
vector<int> edge[maxn];
vector<int> pat[maxn];
int range[maxn][2], ransum;
int ans[maxn];
template <class t>
struct segment_node {
  int be, en;
  t maxv, add, sum;
};
template <class t>
struct segment_tree {
  int l;
  segment_node<t> tree[maxn * 4];
  inline int gleft(int no) { return no << 1; }
  inline int gright(int no) { return (no << 1) + 1; }
  inline int gfa(int no) { return no >> 1; }
  inline segment_tree() { l = 0; }
  void build(int no, int l, int r, t orig = 0, t *a = NULL) {
    if (l == r) {
      tree[no].be = tree[no].en = l;
      tree[no].add = 0;
      if (a == NULL)
        tree[no].maxv = orig;
      else
        tree[no].maxv = a[l];
      tree[no].add = 0;
      tree[no].sum = tree[no].maxv;
      return;
    }
    tree[no].be = l;
    tree[no].en = r;
    int mid = (l + r) / 2;
    build(gleft(no), l, mid, orig, a);
    build(gright(no), mid + 1, r, orig, a);
    tree[no].sum = tree[gleft(no)].sum + tree[gright(no)].sum;
    tree[no].add = 0;
    tree[no].maxv = max1(tree[gleft(no)].maxv, tree[gright(no)].maxv);
  }
  void down(int l, int r, int no, t ranadd) {
    if (l <= tree[no].be && r >= tree[no].en) {
      tree[no].add += ranadd;
      return;
    }
    int mid = (tree[no].be + tree[no].en) / 2;
    if (r >= tree[no].be && l <= mid) down(l, r, gleft(no), ranadd);
    if (r >= mid + 1 && l <= tree[no].en) down(l, r, gright(no), ranadd);
    tree[no].sum =
        ((tree[gleft(no)].add ? (tree[gleft(no)].en - tree[gleft(no)].be + 1)
                              : tree[gleft(no)].sum) +
         (tree[gright(no)].add ? (tree[gright(no)].en - tree[gright(no)].be + 1)
                               : tree[gright(no)].sum));
    tree[no].maxv = max1(tree[gleft(no)].maxv, tree[gright(no)].maxv);
  }
  t getsum(int l, int r, int no) {
    if (l > r) return 0;
    if (tree[no].add) return (r - l + 1);
    if (l <= tree[no].be && r >= tree[no].en)
      return tree[no].add ? tree[no].be - tree[no].en + 1 : tree[no].sum;
    t ans = 0;
    int mid = (tree[no].be + tree[no].en) / 2;
    if (r >= tree[no].be && l <= mid)
      ans += getsum(max1(l, tree[no].be), min1(r, mid), gleft(no));
    if (r >= mid + 1 && l <= tree[no].en)
      ans += getsum(max1(l, mid + 1), min1(r, tree[no].en), gright(no));
    return ans;
  }
  int getrank(int rank, int no) {
    if (rank > tree[no].sum) return -1;
    if (tree[no].be == tree[no].en) return tree[no].be;
    int mid = (tree[no].be + tree[no].en) / 2;
    if (rank <= tree[gleft(no)].sum + tree[no].add * (mid - tree[no].be + 1))
      return getrank(rank, gleft(no));
    return getrank(
        rank - (tree[gleft(no)].sum + tree[no].add * (mid - tree[no].be + 1)),
        gright(no));
  }
  inline int section_getrank(int l, int r, int rank) {
    return getrank(rank + getsum(0, l - 1, 1), 1);
  }
};
segment_tree<int> sgt;
void dfs1(int no, int fa) {
  ransum++;
  range[no][0] = ransum;
  for (int i = 0; i < (int)edge[no].size(); i++) {
    if (fa == edge[no][i]) continue;
    dfs1(edge[no][i], no);
  }
  range[no][1] = ransum;
}
void justdoit(int no, int fa) {
  for (int i = 0; i < (int)pat[no].size(); i++) {
    sgt.down(range[no][0], range[no][1], 1, 1);
    sgt.down(range[pat[no][i]][0], range[pat[no][i]][1], 1, 1);
  }
  ans[no] = sgt.tree[1].add ? n - 1 : sgt.tree[1].sum - 1;
  for (int i = 0; i < (int)edge[no].size(); i++) {
    if (fa == edge[no][i]) continue;
    justdoit(edge[no][i], no);
  }
  for (int i = 0; i < (int)pat[no].size(); i++) {
    sgt.down(range[no][0], range[no][1], 1, -1);
    sgt.down(range[pat[no][i]][0], range[pat[no][i]][1], 1, -1);
  }
}
int main() {
  scanf("%d%d", &n, &nq);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  for (int i = 0; i < nq; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    pat[a].push_back(b);
    pat[b].push_back(a);
  }
  dfs1(0, -1);
  sgt.build(1, 0, n + 1);
  justdoit(0, -1);
  for (int i = 0; i < n; i++) printf("%d ", max1(ans[i], 0));
  printf("\n");
  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 double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <class T>
inline T max1(T a, T b) {
  return a > b ? a : b;
}
template <class T>
inline T min1(T a, T b) {
  return a < b ? a : b;
}
template <class T>
inline T gcd1(T a, T b) {
  if (a < b) swap(a, b);
  if (a % b == 0) return b;
  return gcd1(b, a % b);
}
template <class T>
inline T lb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned long long nValue) {
  nValue = ((0xaaaaaaaaaaaaaaaaull & nValue) >> 1) +
           (0x5555555555555555ull & nValue);
  nValue = ((0xccccccccccccccccull & nValue) >> 2) +
           (0x3333333333333333ull & nValue);
  nValue = ((0xf0f0f0f0f0f0f0f0ull & nValue) >> 4) +
           (0x0f0f0f0f0f0f0f0full & nValue);
  nValue = ((0xff00ff00ff00ff00ull & nValue) >> 8) +
           (0x00ff00ff00ff00ffull & nValue);
  nValue = ((0xffff0000ffff0000ull & nValue) >> 16) +
           (0x0000ffff0000ffffull & nValue);
  nValue = ((0xffffffff00000000ull & nValue) >> 32) +
           (0x00000000ffffffffull & nValue);
  return nValue;
}
inline int jud(double a, double b) {
  if (abs1(a - b) < eps) return 0;
  if (a < b) return -1;
  return 1;
}
long long pow(long long n, long long m, long long mod = 0) {
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
const int maxn = 101000;
int n, nq;
vector<int> edge[maxn];
vector<int> pat[maxn];
int range[maxn][2], ransum;
int ans[maxn];
template <class t>
struct segment_node {
  int be, en;
  t maxv, add, sum;
};
template <class t>
struct segment_tree {
  int l;
  segment_node<t> tree[maxn * 4];
  inline int gleft(int no) { return no << 1; }
  inline int gright(int no) { return (no << 1) + 1; }
  inline int gfa(int no) { return no >> 1; }
  inline segment_tree() { l = 0; }
  void build(int no, int l, int r, t orig = 0, t *a = NULL) {
    if (l == r) {
      tree[no].be = tree[no].en = l;
      tree[no].add = 0;
      if (a == NULL)
        tree[no].maxv = orig;
      else
        tree[no].maxv = a[l];
      tree[no].add = 0;
      tree[no].sum = tree[no].maxv;
      return;
    }
    tree[no].be = l;
    tree[no].en = r;
    int mid = (l + r) / 2;
    build(gleft(no), l, mid, orig, a);
    build(gright(no), mid + 1, r, orig, a);
    tree[no].sum = tree[gleft(no)].sum + tree[gright(no)].sum;
    tree[no].add = 0;
    tree[no].maxv = max1(tree[gleft(no)].maxv, tree[gright(no)].maxv);
  }
  void down(int l, int r, int no, t ranadd) {
    if (l <= tree[no].be && r >= tree[no].en) {
      tree[no].add += ranadd;
      return;
    }
    int mid = (tree[no].be + tree[no].en) / 2;
    if (r >= tree[no].be && l <= mid) down(l, r, gleft(no), ranadd);
    if (r >= mid + 1 && l <= tree[no].en) down(l, r, gright(no), ranadd);
    tree[no].sum =
        ((tree[gleft(no)].add ? (tree[gleft(no)].en - tree[gleft(no)].be + 1)
                              : tree[gleft(no)].sum) +
         (tree[gright(no)].add ? (tree[gright(no)].en - tree[gright(no)].be + 1)
                               : tree[gright(no)].sum));
    tree[no].maxv = max1(tree[gleft(no)].maxv, tree[gright(no)].maxv);
  }
  t getsum(int l, int r, int no) {
    if (l > r) return 0;
    if (tree[no].add) return (r - l + 1);
    if (l <= tree[no].be && r >= tree[no].en)
      return tree[no].add ? tree[no].be - tree[no].en + 1 : tree[no].sum;
    t ans = 0;
    int mid = (tree[no].be + tree[no].en) / 2;
    if (r >= tree[no].be && l <= mid)
      ans += getsum(max1(l, tree[no].be), min1(r, mid), gleft(no));
    if (r >= mid + 1 && l <= tree[no].en)
      ans += getsum(max1(l, mid + 1), min1(r, tree[no].en), gright(no));
    return ans;
  }
  int getrank(int rank, int no) {
    if (rank > tree[no].sum) return -1;
    if (tree[no].be == tree[no].en) return tree[no].be;
    int mid = (tree[no].be + tree[no].en) / 2;
    if (rank <= tree[gleft(no)].sum + tree[no].add * (mid - tree[no].be + 1))
      return getrank(rank, gleft(no));
    return getrank(
        rank - (tree[gleft(no)].sum + tree[no].add * (mid - tree[no].be + 1)),
        gright(no));
  }
  inline int section_getrank(int l, int r, int rank) {
    return getrank(rank + getsum(0, l - 1, 1), 1);
  }
};
segment_tree<int> sgt;
void dfs1(int no, int fa) {
  ransum++;
  range[no][0] = ransum;
  for (int i = 0; i < (int)edge[no].size(); i++) {
    if (fa == edge[no][i]) continue;
    dfs1(edge[no][i], no);
  }
  range[no][1] = ransum;
}
void justdoit(int no, int fa) {
  for (int i = 0; i < (int)pat[no].size(); i++) {
    sgt.down(range[no][0], range[no][1], 1, 1);
    sgt.down(range[pat[no][i]][0], range[pat[no][i]][1], 1, 1);
  }
  ans[no] = sgt.tree[1].add ? n - 1 : sgt.tree[1].sum - 1;
  for (int i = 0; i < (int)edge[no].size(); i++) {
    if (fa == edge[no][i]) continue;
    justdoit(edge[no][i], no);
  }
  for (int i = 0; i < (int)pat[no].size(); i++) {
    sgt.down(range[no][0], range[no][1], 1, -1);
    sgt.down(range[pat[no][i]][0], range[pat[no][i]][1], 1, -1);
  }
}
int main() {
  scanf("%d%d", &n, &nq);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  for (int i = 0; i < nq; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    pat[a].push_back(b);
    pat[b].push_back(a);
  }
  dfs1(0, -1);
  sgt.build(1, 0, n + 1);
  justdoit(0, -1);
  for (int i = 0; i < n; i++) printf("%d ", max1(ans[i], 0));
  printf("\n");
  return 0;
}

```