#include <bits/stdc++.h>
using namespace std;
const int N = 1000 * 100 + 10, INF = 1000 * 1000 * 1000;
int st[N], en[N], ans[N], sum[N * 4], minn[N * 4], lazy[N * 4], start, n;
bool mark[N];
vector<int> adj[N], qr[N];
void DFS1(int v) {
  mark[v] = 1;
  st[v] = start++;
  for (int u : adj[v])
    if (!mark[u]) DFS1(u);
  en[v] = start;
  return;
}
void shift(int ind) {
  int a = lazy[ind];
  lazy[ind] = 0;
  minn[ind * 2] += a;
  minn[ind * 2 + 1] += a;
  lazy[ind * 2] += a;
  lazy[ind * 2 + 1] += a;
  return;
}
void add(int l, int r, int val, int b = 0, int e = n, int ind = 1) {
  if (l <= b && e <= r) {
    minn[ind] += val;
    lazy[ind] += val;
    return;
  }
  int mid = (b + e) / 2;
  shift(ind);
  if (l < mid) add(l, r, val, b, mid, ind * 2);
  if (r > mid) add(l, r, val, mid, e, ind * 2 + 1);
  minn[ind] = min(minn[ind * 2], minn[ind * 2 + 1]);
  if (minn[ind * 2] < minn[ind * 2 + 1])
    sum[ind] = sum[ind * 2];
  else if (minn[ind * 2 + 1] < minn[ind * 2])
    sum[ind] = sum[ind * 2 + 1];
  else
    sum[ind] = sum[ind * 2 + 1] + sum[ind * 2];
  return;
}
void DFS2(int v) {
  mark[v] = 1;
  for (int u : qr[v]) {
    add(st[u], en[u], 1);
    add(st[v], en[v], 1);
  }
  ans[v] = (minn[1] ? n : n - sum[1]) - 1;
  for (int u : adj[v]) {
    if (!mark[u]) DFS2(u);
  }
  for (int u : qr[v]) {
    add(st[u], en[u], -1);
    add(st[v], en[v], -1);
  }
  return;
}
void Make(int b = 0, int e = n, int ind = 1) {
  if (b + 1 == e) {
    sum[ind] = 1;
    return;
  }
  int mid = (b + e) / 2;
  Make(b, mid, ind * 2);
  Make(mid, e, ind * 2 + 1);
  sum[ind] = e - b;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int q, u, v;
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  DFS1(0);
  for (int i = 0; i < q; i++) {
    cin >> u >> v;
    u--, v--;
    qr[u].push_back(v);
    qr[v].push_back(u);
  }
  fill(mark, mark + n, 0);
  Make();
  DFS2(0);
  for (int i = 0; i < n; i++) cout << (ans[i] < 0 ? 0 : ans[i]) << endl;
  return 0;
}

### Prompt

Please formulate 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;
const int N = 1000 * 100 + 10, INF = 1000 * 1000 * 1000;
int st[N], en[N], ans[N], sum[N * 4], minn[N * 4], lazy[N * 4], start, n;
bool mark[N];
vector<int> adj[N], qr[N];
void DFS1(int v) {
  mark[v] = 1;
  st[v] = start++;
  for (int u : adj[v])
    if (!mark[u]) DFS1(u);
  en[v] = start;
  return;
}
void shift(int ind) {
  int a = lazy[ind];
  lazy[ind] = 0;
  minn[ind * 2] += a;
  minn[ind * 2 + 1] += a;
  lazy[ind * 2] += a;
  lazy[ind * 2 + 1] += a;
  return;
}
void add(int l, int r, int val, int b = 0, int e = n, int ind = 1) {
  if (l <= b && e <= r) {
    minn[ind] += val;
    lazy[ind] += val;
    return;
  }
  int mid = (b + e) / 2;
  shift(ind);
  if (l < mid) add(l, r, val, b, mid, ind * 2);
  if (r > mid) add(l, r, val, mid, e, ind * 2 + 1);
  minn[ind] = min(minn[ind * 2], minn[ind * 2 + 1]);
  if (minn[ind * 2] < minn[ind * 2 + 1])
    sum[ind] = sum[ind * 2];
  else if (minn[ind * 2 + 1] < minn[ind * 2])
    sum[ind] = sum[ind * 2 + 1];
  else
    sum[ind] = sum[ind * 2 + 1] + sum[ind * 2];
  return;
}
void DFS2(int v) {
  mark[v] = 1;
  for (int u : qr[v]) {
    add(st[u], en[u], 1);
    add(st[v], en[v], 1);
  }
  ans[v] = (minn[1] ? n : n - sum[1]) - 1;
  for (int u : adj[v]) {
    if (!mark[u]) DFS2(u);
  }
  for (int u : qr[v]) {
    add(st[u], en[u], -1);
    add(st[v], en[v], -1);
  }
  return;
}
void Make(int b = 0, int e = n, int ind = 1) {
  if (b + 1 == e) {
    sum[ind] = 1;
    return;
  }
  int mid = (b + e) / 2;
  Make(b, mid, ind * 2);
  Make(mid, e, ind * 2 + 1);
  sum[ind] = e - b;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int q, u, v;
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  DFS1(0);
  for (int i = 0; i < q; i++) {
    cin >> u >> v;
    u--, v--;
    qr[u].push_back(v);
    qr[v].push_back(u);
  }
  fill(mark, mark + n, 0);
  Make();
  DFS2(0);
  for (int i = 0; i < n; i++) cout << (ans[i] < 0 ? 0 : ans[i]) << endl;
  return 0;
}

```