#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, mark[N];
int uL[N], uR[N], par[N], dep[N], vis[N], pos[N], segID;
vector<int> adj[N];
vector<int> partner[N];
struct node {
  int sum, lazy;
  node *left, *right;
  node(node *left = NULL, node *right = NULL) : left(left), right(right) {
    sum = 0;
    lazy = -1;
    if (left) sum += left->sum;
    if (right) sum += right->sum;
  }
} *null = new node();
node *push(node *p, int L, int R) {
  if (L < R && ~p->lazy) {
    node *l = new node(), *r = new node();
    l->sum = p->lazy * (((L + R) >> 1) - L + 1);
    r->sum = p->lazy * (R - ((L + R) >> 1));
    l->lazy = r->lazy = p->lazy;
    p->left = l;
    p->right = r;
    p->lazy = -1;
  }
  return p;
}
node *insert(int a, int b, int x, node *p, int L = 0, int R = n - 1) {
  if (b < L || R < a) return p;
  if (!p) p = null;
  if (a <= L && R <= b) {
    p = new node();
    p->sum = (R - L + 1) * x;
    p->lazy = x;
    return p;
  }
  if (~p->lazy) return p;
  return new node(insert(a, b, x, p->left, L, ((L + R) >> 1)),
                  insert(a, b, x, p->right, ((L + R) >> 1) + 1, R));
}
void dfs(int u) {
  uL[u] = segID++;
  for (int i = 0; i < adj[u].size(); ++i) {
    int v = adj[u][i];
    if (par[u] != v) {
      dep[v] = dep[u] + 1;
      par[v] = u;
      dfs(v);
    }
  }
  uR[u] = segID - 1;
}
node *tree[N];
void dfs2(int u) {
  tree[u] = tree[par[u]];
  for (int i = 0; i < partner[u].size(); ++i) {
    int v = partner[u][i];
    tree[u] = insert(uL[v], uR[v], 1, tree[u]);
  }
  if (mark[u]) tree[u] = insert(uL[u], uR[u], 1, tree[u]);
  mark[u] |= mark[par[u]];
  for (int i = 0; i < adj[u].size(); ++i) {
    int v = adj[u][i];
    if (par[u] != v) dfs2(v);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  while (m--) {
    int u, v;
    cin >> u >> v;
    mark[u] = mark[v] = true;
    partner[u].push_back(v);
    partner[v].push_back(u);
  }
  tree[0] = null;
  dfs(1);
  dfs2(1);
  for (int i = 1; i <= n; ++i) {
    cout << (tree[i] ? tree[i]->sum : 0) - mark[i] << " \n"[i == n];
  }
  cout << flush;
}

### Prompt

Please create a solution in CPP 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 int N = 100005;
int n, m, mark[N];
int uL[N], uR[N], par[N], dep[N], vis[N], pos[N], segID;
vector<int> adj[N];
vector<int> partner[N];
struct node {
  int sum, lazy;
  node *left, *right;
  node(node *left = NULL, node *right = NULL) : left(left), right(right) {
    sum = 0;
    lazy = -1;
    if (left) sum += left->sum;
    if (right) sum += right->sum;
  }
} *null = new node();
node *push(node *p, int L, int R) {
  if (L < R && ~p->lazy) {
    node *l = new node(), *r = new node();
    l->sum = p->lazy * (((L + R) >> 1) - L + 1);
    r->sum = p->lazy * (R - ((L + R) >> 1));
    l->lazy = r->lazy = p->lazy;
    p->left = l;
    p->right = r;
    p->lazy = -1;
  }
  return p;
}
node *insert(int a, int b, int x, node *p, int L = 0, int R = n - 1) {
  if (b < L || R < a) return p;
  if (!p) p = null;
  if (a <= L && R <= b) {
    p = new node();
    p->sum = (R - L + 1) * x;
    p->lazy = x;
    return p;
  }
  if (~p->lazy) return p;
  return new node(insert(a, b, x, p->left, L, ((L + R) >> 1)),
                  insert(a, b, x, p->right, ((L + R) >> 1) + 1, R));
}
void dfs(int u) {
  uL[u] = segID++;
  for (int i = 0; i < adj[u].size(); ++i) {
    int v = adj[u][i];
    if (par[u] != v) {
      dep[v] = dep[u] + 1;
      par[v] = u;
      dfs(v);
    }
  }
  uR[u] = segID - 1;
}
node *tree[N];
void dfs2(int u) {
  tree[u] = tree[par[u]];
  for (int i = 0; i < partner[u].size(); ++i) {
    int v = partner[u][i];
    tree[u] = insert(uL[v], uR[v], 1, tree[u]);
  }
  if (mark[u]) tree[u] = insert(uL[u], uR[u], 1, tree[u]);
  mark[u] |= mark[par[u]];
  for (int i = 0; i < adj[u].size(); ++i) {
    int v = adj[u][i];
    if (par[u] != v) dfs2(v);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  while (m--) {
    int u, v;
    cin >> u >> v;
    mark[u] = mark[v] = true;
    partner[u].push_back(v);
    partner[v].push_back(u);
  }
  tree[0] = null;
  dfs(1);
  dfs2(1);
  for (int i = 1; i <= n; ++i) {
    cout << (tree[i] ? tree[i]->sum : 0) - mark[i] << " \n"[i == n];
  }
  cout << flush;
}

```