#include <bits/stdc++.h>
using namespace std;
struct node {
  int val, add;
  node() {
    val = 0;
    add = 0;
  }
} it[1 << 20];
int ls[1 << 18], rs[1 << 18], dfsInd, n, q, par[1 << 18], k = 19, ans[1 << 18];
vector<int> qs[1 << 18], chs[1 << 18];
void dfs(int x) {
  ls[x] = dfsInd++;
  for (int i = 0; i < chs[x].size(); i++) {
    if (chs[x][i] == par[x]) {
      swap(chs[x][i], chs[x][chs[x].size() - 1]);
    }
    if (chs[x][i] == par[x]) {
      break;
    }
    par[chs[x][i]] = x;
    dfs(chs[x][i]);
  }
  if (chs[x].back() == par[x]) {
    chs[x].pop_back();
  }
  rs[x] = dfsInd;
}
void add(int ind, int l, int r, int ll, int rr, int v) {
  if (ll <= l && r <= rr) {
    it[ind].add += v;
    if (it[ind].add) {
      it[ind].val = r - l;
    } else if (l == r - 1) {
      it[ind].val = 0;
    } else {
      it[ind].val = it[ind * 2].val + it[ind * 2 + 1].val;
    }
    return;
  }
  if (r <= ll || rr <= l) {
    return;
  }
  add(ind * 2, l, (l + r) / 2, ll, rr, v);
  add(ind * 2 + 1, (l + r) / 2, r, ll, rr, v);
  if (it[ind].add) {
    it[ind].val = r - l;
  } else {
    it[ind].val = it[ind * 2].val + it[ind * 2 + 1].val;
  }
}
void dfs2(int x) {
  if (qs[x].size()) {
    add(1, 0, (1 << k), ls[x], rs[x], 1);
  }
  for (int i = 0; i < qs[x].size(); i++) {
    add(1, 0, (1 << k), ls[qs[x][i]], rs[qs[x][i]], 1);
  }
  ans[x] = it[1].val;
  if (ans[x]) {
    ans[x]--;
  }
  for (int i = 0; i < chs[x].size(); i++) {
    dfs2(chs[x][i]);
  }
  for (int i = 0; i < qs[x].size(); i++) {
    add(1, 0, (1 << k), ls[qs[x][i]], rs[qs[x][i]], -1);
  }
  if (qs[x].size()) {
    add(1, 0, (1 << k), ls[x], rs[x], -1);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> q;
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    chs[a].push_back(b);
    chs[b].push_back(a);
  }
  dfs(1);
  for (int i = 0; i < q; i++) {
    int a, b;
    cin >> a >> b;
    qs[a].push_back(b);
    qs[b].push_back(a);
  }
  dfs2(1);
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
  cout << "\n";
  return 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;
struct node {
  int val, add;
  node() {
    val = 0;
    add = 0;
  }
} it[1 << 20];
int ls[1 << 18], rs[1 << 18], dfsInd, n, q, par[1 << 18], k = 19, ans[1 << 18];
vector<int> qs[1 << 18], chs[1 << 18];
void dfs(int x) {
  ls[x] = dfsInd++;
  for (int i = 0; i < chs[x].size(); i++) {
    if (chs[x][i] == par[x]) {
      swap(chs[x][i], chs[x][chs[x].size() - 1]);
    }
    if (chs[x][i] == par[x]) {
      break;
    }
    par[chs[x][i]] = x;
    dfs(chs[x][i]);
  }
  if (chs[x].back() == par[x]) {
    chs[x].pop_back();
  }
  rs[x] = dfsInd;
}
void add(int ind, int l, int r, int ll, int rr, int v) {
  if (ll <= l && r <= rr) {
    it[ind].add += v;
    if (it[ind].add) {
      it[ind].val = r - l;
    } else if (l == r - 1) {
      it[ind].val = 0;
    } else {
      it[ind].val = it[ind * 2].val + it[ind * 2 + 1].val;
    }
    return;
  }
  if (r <= ll || rr <= l) {
    return;
  }
  add(ind * 2, l, (l + r) / 2, ll, rr, v);
  add(ind * 2 + 1, (l + r) / 2, r, ll, rr, v);
  if (it[ind].add) {
    it[ind].val = r - l;
  } else {
    it[ind].val = it[ind * 2].val + it[ind * 2 + 1].val;
  }
}
void dfs2(int x) {
  if (qs[x].size()) {
    add(1, 0, (1 << k), ls[x], rs[x], 1);
  }
  for (int i = 0; i < qs[x].size(); i++) {
    add(1, 0, (1 << k), ls[qs[x][i]], rs[qs[x][i]], 1);
  }
  ans[x] = it[1].val;
  if (ans[x]) {
    ans[x]--;
  }
  for (int i = 0; i < chs[x].size(); i++) {
    dfs2(chs[x][i]);
  }
  for (int i = 0; i < qs[x].size(); i++) {
    add(1, 0, (1 << k), ls[qs[x][i]], rs[qs[x][i]], -1);
  }
  if (qs[x].size()) {
    add(1, 0, (1 << k), ls[x], rs[x], -1);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> q;
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    chs[a].push_back(b);
    chs[b].push_back(a);
  }
  dfs(1);
  for (int i = 0; i < q; i++) {
    int a, b;
    cin >> a >> b;
    qs[a].push_back(b);
    qs[b].push_back(a);
  }
  dfs2(1);
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
  cout << "\n";
  return 0;
}

```