#include <bits/stdc++.h>
using namespace std;
int n, m, cnt;
int data[100010][2], ans[100010];
int in_que[100010], size[100010];
vector<int> g[100010];
int ecnt;
struct Edge {
  int to;
  Edge *next;
} * mat[100010], edges[100010 * 2];
void link(int x, int to) {
  edges[ecnt].to = to;
  edges[ecnt].next = mat[x];
  mat[x] = &edges[ecnt++];
}
void dfs(int x, int father) {
  in_que[x] = ++cnt;
  size[x] = 1;
  for (Edge *p = mat[x]; p; p = p->next) {
    int to = p->to;
    if (to == father) continue;
    dfs(to, x);
    size[x] += size[to];
  }
}
struct Segtree {
  int left[100010 * 4], right[100010 * 4];
  int mark[100010 * 4], num[100010 * 4];
  void updata(int step) {
    if (mark[step])
      num[step] = right[step] - left[step] + 1;
    else if (left[step] == right[step])
      num[step] = 0;
    else
      num[step] = num[step * 2] + num[step * 2 + 1];
  }
  void build(int l, int r, int step) {
    left[step] = l, right[step] = r;
    num[step] = mark[step] = 0;
    if (l == r) return;
    int mid = (left[step] + right[step]) >> 1;
    build(l, mid, step * 2);
    build(mid + 1, r, step * 2 + 1);
  }
  void insert(int l, int r, int step, int key) {
    if (left[step] == l && right[step] == r) {
      mark[step] += key;
      updata(step);
      return;
    }
    int mid = (left[step] + right[step]) >> 1;
    if (r <= mid)
      insert(l, r, step * 2, key);
    else if (l > mid)
      insert(l, r, step * 2 + 1, key);
    else
      insert(l, mid, step * 2, key), insert(mid + 1, r, step * 2 + 1, key);
    updata(step);
  }
} tree;
void solve(int x, int father) {
  for (int i = 0, k; i < g[x].size(); i++) {
    k = data[g[x][i]][0];
    tree.insert(in_que[k], in_que[k] + size[k] - 1, 1, 1);
    k = data[g[x][i]][1];
    tree.insert(in_que[k], in_que[k] + size[k] - 1, 1, 1);
  }
  ans[x] = tree.num[1];
  if (ans[x]) ans[x]--;
  for (Edge *p = mat[x]; p; p = p->next) {
    int to = p->to;
    if (to == father) continue;
    solve(to, x);
  }
  for (int i = 0, k; i < g[x].size(); i++) {
    k = data[g[x][i]][0];
    tree.insert(in_que[k], in_que[k] + size[k] - 1, 1, -1);
    k = data[g[x][i]][1];
    tree.insert(in_que[k], in_que[k] + size[k] - 1, 1, -1);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    link(x, y);
    link(y, x);
  }
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &data[i][0], &data[i][1]);
    g[data[i][0]].push_back(i);
    g[data[i][1]].push_back(i);
  }
  dfs(1, -1);
  tree.build(1, n, 1);
  solve(1, -1);
  for (int i = 1; i <= n; i++) printf("%d%c", ans[i], i == n ? '\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>
using namespace std;
int n, m, cnt;
int data[100010][2], ans[100010];
int in_que[100010], size[100010];
vector<int> g[100010];
int ecnt;
struct Edge {
  int to;
  Edge *next;
} * mat[100010], edges[100010 * 2];
void link(int x, int to) {
  edges[ecnt].to = to;
  edges[ecnt].next = mat[x];
  mat[x] = &edges[ecnt++];
}
void dfs(int x, int father) {
  in_que[x] = ++cnt;
  size[x] = 1;
  for (Edge *p = mat[x]; p; p = p->next) {
    int to = p->to;
    if (to == father) continue;
    dfs(to, x);
    size[x] += size[to];
  }
}
struct Segtree {
  int left[100010 * 4], right[100010 * 4];
  int mark[100010 * 4], num[100010 * 4];
  void updata(int step) {
    if (mark[step])
      num[step] = right[step] - left[step] + 1;
    else if (left[step] == right[step])
      num[step] = 0;
    else
      num[step] = num[step * 2] + num[step * 2 + 1];
  }
  void build(int l, int r, int step) {
    left[step] = l, right[step] = r;
    num[step] = mark[step] = 0;
    if (l == r) return;
    int mid = (left[step] + right[step]) >> 1;
    build(l, mid, step * 2);
    build(mid + 1, r, step * 2 + 1);
  }
  void insert(int l, int r, int step, int key) {
    if (left[step] == l && right[step] == r) {
      mark[step] += key;
      updata(step);
      return;
    }
    int mid = (left[step] + right[step]) >> 1;
    if (r <= mid)
      insert(l, r, step * 2, key);
    else if (l > mid)
      insert(l, r, step * 2 + 1, key);
    else
      insert(l, mid, step * 2, key), insert(mid + 1, r, step * 2 + 1, key);
    updata(step);
  }
} tree;
void solve(int x, int father) {
  for (int i = 0, k; i < g[x].size(); i++) {
    k = data[g[x][i]][0];
    tree.insert(in_que[k], in_que[k] + size[k] - 1, 1, 1);
    k = data[g[x][i]][1];
    tree.insert(in_que[k], in_que[k] + size[k] - 1, 1, 1);
  }
  ans[x] = tree.num[1];
  if (ans[x]) ans[x]--;
  for (Edge *p = mat[x]; p; p = p->next) {
    int to = p->to;
    if (to == father) continue;
    solve(to, x);
  }
  for (int i = 0, k; i < g[x].size(); i++) {
    k = data[g[x][i]][0];
    tree.insert(in_que[k], in_que[k] + size[k] - 1, 1, -1);
    k = data[g[x][i]][1];
    tree.insert(in_que[k], in_que[k] + size[k] - 1, 1, -1);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    link(x, y);
    link(y, x);
  }
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &data[i][0], &data[i][1]);
    g[data[i][0]].push_back(i);
    g[data[i][1]].push_back(i);
  }
  dfs(1, -1);
  tree.build(1, n, 1);
  solve(1, -1);
  for (int i = 1; i <= n; i++) printf("%d%c", ans[i], i == n ? '\n' : ' ');
  return 0;
}

```