#include <bits/stdc++.h>
using namespace std;
const int sz = 1e5 + 10;
vector<int> g[sz], got[sz];
struct qnode {
  int a, b;
} qry[sz];
int tim, n, m, start[sz], stop[sz], ans[sz];
const int psz = 4 * sz + sz * 120;
int root[psz], val[psz], lazy[psz], Left[psz], Right[psz], per = 0;
void build(int lo, int hi, int node) {
  if (lo == hi) {
    val[node] = 0, lazy[node] = -1;
    return;
  }
  int mid = lo + hi >> 1;
  Left[node] = ++per, Right[node] = ++per;
  if (per >= psz) {
    cout << "LOL" << endl;
    exit(0);
  }
  build(lo, mid, Left[node]);
  build(mid + 1, hi, Right[node]);
  val[node] = 0, lazy[node] = -1;
}
int update_prop(int l, int r, int v, int node) {
  int nnode = ++per;
  if (per >= psz) {
    cout << "in lazy" << endl;
    exit(0);
  }
  val[nnode] = (r - l + 1) * v;
  lazy[nnode] = v;
  Left[nnode] = Left[node], Right[nnode] = Right[node];
  return nnode;
}
int update(int lo, int hi, int l, int r, int v, int node) {
  if (lo > r || hi < l) return node;
  int nnode = ++per;
  if (per >= psz) {
    cout << "LOL in update" << endl;
    exit(0);
  }
  if (lo >= l && hi <= r) {
    val[nnode] = (hi - lo + 1) * v;
    lazy[nnode] = v;
    Left[nnode] = Left[node];
    Right[nnode] = Right[node];
    return nnode;
  }
  int mid = lo + hi >> 1;
  lazy[nnode] = lazy[node], Left[nnode] = Left[node],
  Right[nnode] = Right[node];
  if (lazy[nnode] != -1) {
    Left[nnode] = update_prop(lo, mid, lazy[nnode], Left[nnode]);
    Right[nnode] = update_prop(mid + 1, hi, lazy[nnode], Right[nnode]);
    lazy[nnode] = -1;
  }
  Left[nnode] = update(lo, mid, l, r, v, Left[nnode]);
  Right[nnode] = update(mid + 1, hi, l, r, v, Right[nnode]);
  val[nnode] = val[Left[nnode]] + val[Right[nnode]];
  return nnode;
}
void dfs(int u, int p) {
  start[u] = ++tim;
  for (int &v : g[u]) {
    if (v == p) continue;
    dfs(v, u);
  }
  stop[u] = tim;
}
void ans_dfs(int u, int p) {
  root[u] = root[p];
  for (int &idx : got[u]) {
    int a = qry[idx].a, b = qry[idx].b;
    root[u] = update(1, tim, start[a], stop[a], 1, root[u]);
    root[u] = update(1, tim, start[b], stop[b], 1, root[u]);
  }
  int lastPer = per;
  ans[u] = val[root[u]] - 1;
  for (int &v : g[u]) {
    if (v == p) continue;
    ans_dfs(v, u);
  }
  per = lastPer;
}
int main() {
  cin >> n >> m;
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d", &u), scanf("%d", &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d", &a), scanf("%d", &b);
    qry[i] = {a, b};
    got[a].push_back(i), got[b].push_back(i);
  }
  dfs(1, -1);
  root[0] = ++per;
  build(1, tim, root[0]);
  ans_dfs(1, 0);
  for (int i = 1; i <= n; i++) {
    if (i != 1) printf(" ");
    printf("%d", ans[i] == -1 ? 0 : ans[i]);
  }
  printf("\n");
  return 0;
}

### Prompt

Generate 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 sz = 1e5 + 10;
vector<int> g[sz], got[sz];
struct qnode {
  int a, b;
} qry[sz];
int tim, n, m, start[sz], stop[sz], ans[sz];
const int psz = 4 * sz + sz * 120;
int root[psz], val[psz], lazy[psz], Left[psz], Right[psz], per = 0;
void build(int lo, int hi, int node) {
  if (lo == hi) {
    val[node] = 0, lazy[node] = -1;
    return;
  }
  int mid = lo + hi >> 1;
  Left[node] = ++per, Right[node] = ++per;
  if (per >= psz) {
    cout << "LOL" << endl;
    exit(0);
  }
  build(lo, mid, Left[node]);
  build(mid + 1, hi, Right[node]);
  val[node] = 0, lazy[node] = -1;
}
int update_prop(int l, int r, int v, int node) {
  int nnode = ++per;
  if (per >= psz) {
    cout << "in lazy" << endl;
    exit(0);
  }
  val[nnode] = (r - l + 1) * v;
  lazy[nnode] = v;
  Left[nnode] = Left[node], Right[nnode] = Right[node];
  return nnode;
}
int update(int lo, int hi, int l, int r, int v, int node) {
  if (lo > r || hi < l) return node;
  int nnode = ++per;
  if (per >= psz) {
    cout << "LOL in update" << endl;
    exit(0);
  }
  if (lo >= l && hi <= r) {
    val[nnode] = (hi - lo + 1) * v;
    lazy[nnode] = v;
    Left[nnode] = Left[node];
    Right[nnode] = Right[node];
    return nnode;
  }
  int mid = lo + hi >> 1;
  lazy[nnode] = lazy[node], Left[nnode] = Left[node],
  Right[nnode] = Right[node];
  if (lazy[nnode] != -1) {
    Left[nnode] = update_prop(lo, mid, lazy[nnode], Left[nnode]);
    Right[nnode] = update_prop(mid + 1, hi, lazy[nnode], Right[nnode]);
    lazy[nnode] = -1;
  }
  Left[nnode] = update(lo, mid, l, r, v, Left[nnode]);
  Right[nnode] = update(mid + 1, hi, l, r, v, Right[nnode]);
  val[nnode] = val[Left[nnode]] + val[Right[nnode]];
  return nnode;
}
void dfs(int u, int p) {
  start[u] = ++tim;
  for (int &v : g[u]) {
    if (v == p) continue;
    dfs(v, u);
  }
  stop[u] = tim;
}
void ans_dfs(int u, int p) {
  root[u] = root[p];
  for (int &idx : got[u]) {
    int a = qry[idx].a, b = qry[idx].b;
    root[u] = update(1, tim, start[a], stop[a], 1, root[u]);
    root[u] = update(1, tim, start[b], stop[b], 1, root[u]);
  }
  int lastPer = per;
  ans[u] = val[root[u]] - 1;
  for (int &v : g[u]) {
    if (v == p) continue;
    ans_dfs(v, u);
  }
  per = lastPer;
}
int main() {
  cin >> n >> m;
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d", &u), scanf("%d", &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d", &a), scanf("%d", &b);
    qry[i] = {a, b};
    got[a].push_back(i), got[b].push_back(i);
  }
  dfs(1, -1);
  root[0] = ++per;
  build(1, tim, root[0]);
  ans_dfs(1, 0);
  for (int i = 1; i <= n; i++) {
    if (i != 1) printf(" ");
    printf("%d", ans[i] == -1 ? 0 : ans[i]);
  }
  printf("\n");
  return 0;
}

```