#include <bits/stdc++.h>
using namespace std;
int timer, k[100100], o[100100], z, ans[100100];
vector<int> g[100100];
vector<pair<int, int> > q[100100];
pair<int, int> t[400100];
void dfs(int v, int p) {
  for (int i = 0; i < g[v].size(); i++)
    if (g[v][i] != p) {
      dfs(g[v][i], v);
      o[v] += o[g[v][i]];
    }
  o[v]++;
  k[v] = ++timer;
}
void modify(int l, int r, int lv, int rv, int v, int d, int x) {
  if (l > rv || r < lv) return;
  if (lv >= l && rv <= r) {
    t[v].first += d;
    if (t[v].first > 0)
      t[v].second = x;
    else {
      if (lv == rv)
        t[v].second = 0;
      else
        t[v].second = t[v * 2].second + t[v * 2 + 1].second;
    }
    return;
  }
  modify(l, r, lv, (lv + rv) / 2, v * 2, d, x / 2);
  modify(l, r, (lv + rv) / 2 + 1, rv, v * 2 + 1, d, x / 2);
  if (t[v].first > 0)
    t[v].second = x;
  else {
    if (lv == rv)
      t[v].second = 0;
    else
      t[v].second = t[v * 2].second + t[v * 2 + 1].second;
  }
}
void dfs2(int v, int p) {
  for (int i = 0; i < q[v].size(); i++) {
    modify(q[v][i].first, q[v][i].second, 1, z, 1, 1, z);
  }
  ans[v] = t[1].second - (t[1].second > 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 < q[v].size(); i++)
    modify(q[v][i].first, q[v][i].second, 1, z, 1, -1, z);
}
int main() {
  ios_base::sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1, 0);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    q[a].push_back(make_pair(k[b] - o[b] + 1, k[b]));
    q[b].push_back(make_pair(k[a] - o[a] + 1, k[a]));
    q[b].push_back(make_pair(k[b] - o[b] + 1, k[b]));
    q[a].push_back(make_pair(k[a] - o[a] + 1, k[a]));
  }
  z = 1;
  while (z < n) z *= 2;
  dfs2(1, 0);
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
  return 0;
}

### Prompt

Create a solution in Cpp for 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;
int timer, k[100100], o[100100], z, ans[100100];
vector<int> g[100100];
vector<pair<int, int> > q[100100];
pair<int, int> t[400100];
void dfs(int v, int p) {
  for (int i = 0; i < g[v].size(); i++)
    if (g[v][i] != p) {
      dfs(g[v][i], v);
      o[v] += o[g[v][i]];
    }
  o[v]++;
  k[v] = ++timer;
}
void modify(int l, int r, int lv, int rv, int v, int d, int x) {
  if (l > rv || r < lv) return;
  if (lv >= l && rv <= r) {
    t[v].first += d;
    if (t[v].first > 0)
      t[v].second = x;
    else {
      if (lv == rv)
        t[v].second = 0;
      else
        t[v].second = t[v * 2].second + t[v * 2 + 1].second;
    }
    return;
  }
  modify(l, r, lv, (lv + rv) / 2, v * 2, d, x / 2);
  modify(l, r, (lv + rv) / 2 + 1, rv, v * 2 + 1, d, x / 2);
  if (t[v].first > 0)
    t[v].second = x;
  else {
    if (lv == rv)
      t[v].second = 0;
    else
      t[v].second = t[v * 2].second + t[v * 2 + 1].second;
  }
}
void dfs2(int v, int p) {
  for (int i = 0; i < q[v].size(); i++) {
    modify(q[v][i].first, q[v][i].second, 1, z, 1, 1, z);
  }
  ans[v] = t[1].second - (t[1].second > 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 < q[v].size(); i++)
    modify(q[v][i].first, q[v][i].second, 1, z, 1, -1, z);
}
int main() {
  ios_base::sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1, 0);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    q[a].push_back(make_pair(k[b] - o[b] + 1, k[b]));
    q[b].push_back(make_pair(k[a] - o[a] + 1, k[a]));
    q[b].push_back(make_pair(k[b] - o[b] + 1, k[b]));
    q[a].push_back(make_pair(k[a] - o[a] + 1, k[a]));
  }
  z = 1;
  while (z < n) z *= 2;
  dfs2(1, 0);
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
  return 0;
}

```