#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
const int maxN = 101000;
pair<int, int> t[4 * maxN];
int add[4 * maxN];
pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
  if (a.first < b.first) {
    return a;
  }
  if (a.first > b.first) {
    return b;
  }
  return make_pair(a.first, a.second + b.second);
}
void build(int v, int cl, int cr) {
  if (cl == cr) {
    t[v] = make_pair(0, 1);
    return;
  }
  int mid = (cl + cr) / 2;
  build(2 * v, cl, mid);
  build(2 * v + 1, mid + 1, cr);
  t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void push(int v, int cl, int cr) {
  int mid = (cl + cr) / 2;
  add[2 * v] += add[v];
  add[2 * v + 1] += add[v];
  t[2 * v].first += add[v];
  t[2 * v + 1].first += add[v];
  add[v] = 0;
}
void update(int v, int cl, int cr, int tl, int tr, int value) {
  if (cl == tl && cr == tr) {
    add[v] += value;
    t[v].first += value;
    return;
  }
  int mid = (cl + cr) / 2;
  push(v, cl, cr);
  if (tl > mid) {
    update(2 * v + 1, mid + 1, cr, tl, tr, value);
  } else if (tr <= mid) {
    update(2 * v, cl, mid, tl, tr, value);
  } else {
    update(2 * v, cl, mid, tl, mid, value);
    update(2 * v + 1, mid + 1, cr, mid + 1, tr, value);
  }
  t[v] = merge(t[2 * v], t[2 * v + 1]);
}
pair<int, int> get(int v, int cl, int cr, int tl, int tr) {
  if (cl == tl && cr == tr) {
    return t[v];
  }
  int mid = (cl + cr) / 2;
  push(v, cl, cr);
  if (tl > mid) return get(2 * v + 1, mid + 1, cr, tl, tr);
  if (tr <= mid) return get(2 * v, cl, mid, tl, tr);
  return merge(get(2 * v, cl, mid, tl, mid),
               get(2 * v + 1, mid + 1, cr, mid + 1, tr));
}
vector<int> g[maxN];
vector<int> opers[maxN];
vector<int> cols[maxN];
int n, m;
vector<int> order;
int inv[maxN];
int l[maxN], r[maxN];
void dfs(int v, int p = -1) {
  order.push_back(v);
  l[v] = v;
  for (int i = 0; i < g[v].size(); ++i) {
    if (g[v][i] != p) {
      dfs(g[v][i], v);
    }
  }
  r[v] = v;
  for (int i = 0; i < g[v].size(); ++i) {
    if (g[v][i] != p) {
      r[v] = r[g[v][i]];
    }
  }
}
int res[maxN];
void dfs2(int v, int p = -1) {
  for (int i = 0; i < opers[v].size(); ++i) {
    int ccol = opers[v][i];
    for (int j = 0; j < cols[ccol].size(); ++j) {
      int t = cols[ccol][j];
      update(1, 0, n - 1, l[t], r[t], +1);
    }
  }
  pair<int, int> cres = get(1, 0, n - 1, 0, n - 1);
  res[v] = cres.second;
  if (cres.first != 0) {
    res[v] = 0;
  }
  for (int i = 0; i < g[v].size(); ++i) {
    if (g[v][i] != p) {
      dfs2(g[v][i], v);
    }
  }
  for (int i = 0; i < opers[v].size(); ++i) {
    int ccol = opers[v][i];
    for (int j = 0; j < cols[ccol].size(); ++j) {
      int t = cols[ccol][j];
      update(1, 0, n - 1, l[t], r[t], -1);
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  build(1, 0, n - 1);
  for (int i = 1; i < n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1);
  for (int i = 0; i < order.size(); ++i) {
    inv[order[i]] = i;
  }
  for (int i = 1; i <= n; ++i) {
    l[i] = inv[l[i]];
    r[i] = inv[r[i]];
  }
  for (int i = 0; i < m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    cols[i].push_back(x);
    cols[i].push_back(y);
    opers[x].push_back(i);
    opers[y].push_back(i);
  }
  dfs2(1);
  for (int i = 1; i <= n; ++i) {
    int val = n - res[i];
    if (val > 0) --val;
    printf("%d ", val);
  }
  printf("\n");
  return 0;
}

### Prompt

Your task is to create 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 comment(linker, "/STACK:256000000")
using namespace std;
const int maxN = 101000;
pair<int, int> t[4 * maxN];
int add[4 * maxN];
pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
  if (a.first < b.first) {
    return a;
  }
  if (a.first > b.first) {
    return b;
  }
  return make_pair(a.first, a.second + b.second);
}
void build(int v, int cl, int cr) {
  if (cl == cr) {
    t[v] = make_pair(0, 1);
    return;
  }
  int mid = (cl + cr) / 2;
  build(2 * v, cl, mid);
  build(2 * v + 1, mid + 1, cr);
  t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void push(int v, int cl, int cr) {
  int mid = (cl + cr) / 2;
  add[2 * v] += add[v];
  add[2 * v + 1] += add[v];
  t[2 * v].first += add[v];
  t[2 * v + 1].first += add[v];
  add[v] = 0;
}
void update(int v, int cl, int cr, int tl, int tr, int value) {
  if (cl == tl && cr == tr) {
    add[v] += value;
    t[v].first += value;
    return;
  }
  int mid = (cl + cr) / 2;
  push(v, cl, cr);
  if (tl > mid) {
    update(2 * v + 1, mid + 1, cr, tl, tr, value);
  } else if (tr <= mid) {
    update(2 * v, cl, mid, tl, tr, value);
  } else {
    update(2 * v, cl, mid, tl, mid, value);
    update(2 * v + 1, mid + 1, cr, mid + 1, tr, value);
  }
  t[v] = merge(t[2 * v], t[2 * v + 1]);
}
pair<int, int> get(int v, int cl, int cr, int tl, int tr) {
  if (cl == tl && cr == tr) {
    return t[v];
  }
  int mid = (cl + cr) / 2;
  push(v, cl, cr);
  if (tl > mid) return get(2 * v + 1, mid + 1, cr, tl, tr);
  if (tr <= mid) return get(2 * v, cl, mid, tl, tr);
  return merge(get(2 * v, cl, mid, tl, mid),
               get(2 * v + 1, mid + 1, cr, mid + 1, tr));
}
vector<int> g[maxN];
vector<int> opers[maxN];
vector<int> cols[maxN];
int n, m;
vector<int> order;
int inv[maxN];
int l[maxN], r[maxN];
void dfs(int v, int p = -1) {
  order.push_back(v);
  l[v] = v;
  for (int i = 0; i < g[v].size(); ++i) {
    if (g[v][i] != p) {
      dfs(g[v][i], v);
    }
  }
  r[v] = v;
  for (int i = 0; i < g[v].size(); ++i) {
    if (g[v][i] != p) {
      r[v] = r[g[v][i]];
    }
  }
}
int res[maxN];
void dfs2(int v, int p = -1) {
  for (int i = 0; i < opers[v].size(); ++i) {
    int ccol = opers[v][i];
    for (int j = 0; j < cols[ccol].size(); ++j) {
      int t = cols[ccol][j];
      update(1, 0, n - 1, l[t], r[t], +1);
    }
  }
  pair<int, int> cres = get(1, 0, n - 1, 0, n - 1);
  res[v] = cres.second;
  if (cres.first != 0) {
    res[v] = 0;
  }
  for (int i = 0; i < g[v].size(); ++i) {
    if (g[v][i] != p) {
      dfs2(g[v][i], v);
    }
  }
  for (int i = 0; i < opers[v].size(); ++i) {
    int ccol = opers[v][i];
    for (int j = 0; j < cols[ccol].size(); ++j) {
      int t = cols[ccol][j];
      update(1, 0, n - 1, l[t], r[t], -1);
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  build(1, 0, n - 1);
  for (int i = 1; i < n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1);
  for (int i = 0; i < order.size(); ++i) {
    inv[order[i]] = i;
  }
  for (int i = 1; i <= n; ++i) {
    l[i] = inv[l[i]];
    r[i] = inv[r[i]];
  }
  for (int i = 0; i < m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    cols[i].push_back(x);
    cols[i].push_back(y);
    opers[x].push_back(i);
    opers[y].push_back(i);
  }
  dfs2(1);
  for (int i = 1; i <= n; ++i) {
    int val = n - res[i];
    if (val > 0) --val;
    printf("%d ", val);
  }
  printf("\n");
  return 0;
}

```