#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
const double PI = 3.1415926535897932384626433832795;
const double EPS = 1e-12;
const int inf = 1000000000;
const long long linf = 1000000000000000000LL;
template <class T>
inline T sqr(T x) {
  return x * x;
}
int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
pair<int, int> tree[2100000];
int delta[2100000];
void pre(int k) {
  if (!delta[k]) return;
  tree[k].first += delta[k];
  delta[k * 2 + 1] += delta[k];
  delta[k * 2 + 2] += delta[k];
  delta[k] = 0;
}
pair<int, int> add(pair<int, int> a, pair<int, int> b) {
  if (a.first == b.first) return make_pair(a.first, a.second + b.second);
  return min(a, b);
}
void post(int k) {
  pre(k);
  pre(k * 2 + 1);
  pre(k * 2 + 2);
  tree[k] = add(tree[k * 2 + 1], tree[k * 2 + 2]);
}
void init(int a, int b, int k) {
  if (b == a + 1) {
    tree[k] = make_pair(0, 1);
    return;
  }
  int c = (a + b) / 2;
  init(a, c, k * 2 + 1);
  init(c, b, k * 2 + 2);
  post(k);
}
void inc(int l, int r, int v, int a, int b, int k) {
  pre(k);
  if (l <= a && r >= b) {
    delta[k] += v;
    pre(k);
    return;
  }
  if (l >= b || r <= a) return;
  int c = (a + b) / 2;
  inc(l, r, v, a, c, k * 2 + 1);
  inc(l, r, v, c, b, k * 2 + 2);
  post(k);
}
vector<int> gr[110000];
vector<int> bs[110000];
int pos1[110000];
int pos2[110000];
int cnt;
int n;
int res[110000];
void dfs1(int v, int pr) {
  pos1[v] = cnt++;
  for (int i = 0; i < (((int)(gr[v]).size())); ++i) {
    int p = gr[v][i];
    if (p == pr) continue;
    dfs1(p, v);
  }
  pos2[v] = cnt;
}
void dfs2(int v, int pr) {
  for (int i = 0; i < (((int)(bs[v]).size())); ++i) {
    int p = bs[v][i];
    inc(pos1[v], pos2[v], 1, 0, n, 0);
    inc(pos1[p], pos2[p], 1, 0, n, 0);
  }
  pair<int, int> t = tree[0];
  res[v] = n;
  if (!t.first) res[v] -= t.second;
  for (int i = 0; i < (((int)(gr[v]).size())); ++i) {
    int p = gr[v][i];
    if (p == pr) continue;
    dfs2(p, v);
  }
  for (int i = 0; i < (((int)(bs[v]).size())); ++i) {
    int p = bs[v][i];
    inc(pos1[v], pos2[v], -1, 0, n, 0);
    inc(pos1[p], pos2[p], -1, 0, n, 0);
  }
}
int main() {
  int m;
  cin >> n >> m;
  for (int i = 0; i < (n - 1); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    gr[a].push_back(b);
    gr[b].push_back(a);
  }
  for (int i = 0; i < (m); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    bs[a].push_back(b);
    bs[b].push_back(a);
  }
  init(0, n, 0);
  dfs1(0, -1);
  dfs2(0, -1);
  for (int i = 0; i < (n); ++i) {
    if (res[i]) --res[i];
    printf("%d ", res[i]);
  }
  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>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
const double PI = 3.1415926535897932384626433832795;
const double EPS = 1e-12;
const int inf = 1000000000;
const long long linf = 1000000000000000000LL;
template <class T>
inline T sqr(T x) {
  return x * x;
}
int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
pair<int, int> tree[2100000];
int delta[2100000];
void pre(int k) {
  if (!delta[k]) return;
  tree[k].first += delta[k];
  delta[k * 2 + 1] += delta[k];
  delta[k * 2 + 2] += delta[k];
  delta[k] = 0;
}
pair<int, int> add(pair<int, int> a, pair<int, int> b) {
  if (a.first == b.first) return make_pair(a.first, a.second + b.second);
  return min(a, b);
}
void post(int k) {
  pre(k);
  pre(k * 2 + 1);
  pre(k * 2 + 2);
  tree[k] = add(tree[k * 2 + 1], tree[k * 2 + 2]);
}
void init(int a, int b, int k) {
  if (b == a + 1) {
    tree[k] = make_pair(0, 1);
    return;
  }
  int c = (a + b) / 2;
  init(a, c, k * 2 + 1);
  init(c, b, k * 2 + 2);
  post(k);
}
void inc(int l, int r, int v, int a, int b, int k) {
  pre(k);
  if (l <= a && r >= b) {
    delta[k] += v;
    pre(k);
    return;
  }
  if (l >= b || r <= a) return;
  int c = (a + b) / 2;
  inc(l, r, v, a, c, k * 2 + 1);
  inc(l, r, v, c, b, k * 2 + 2);
  post(k);
}
vector<int> gr[110000];
vector<int> bs[110000];
int pos1[110000];
int pos2[110000];
int cnt;
int n;
int res[110000];
void dfs1(int v, int pr) {
  pos1[v] = cnt++;
  for (int i = 0; i < (((int)(gr[v]).size())); ++i) {
    int p = gr[v][i];
    if (p == pr) continue;
    dfs1(p, v);
  }
  pos2[v] = cnt;
}
void dfs2(int v, int pr) {
  for (int i = 0; i < (((int)(bs[v]).size())); ++i) {
    int p = bs[v][i];
    inc(pos1[v], pos2[v], 1, 0, n, 0);
    inc(pos1[p], pos2[p], 1, 0, n, 0);
  }
  pair<int, int> t = tree[0];
  res[v] = n;
  if (!t.first) res[v] -= t.second;
  for (int i = 0; i < (((int)(gr[v]).size())); ++i) {
    int p = gr[v][i];
    if (p == pr) continue;
    dfs2(p, v);
  }
  for (int i = 0; i < (((int)(bs[v]).size())); ++i) {
    int p = bs[v][i];
    inc(pos1[v], pos2[v], -1, 0, n, 0);
    inc(pos1[p], pos2[p], -1, 0, n, 0);
  }
}
int main() {
  int m;
  cin >> n >> m;
  for (int i = 0; i < (n - 1); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    gr[a].push_back(b);
    gr[b].push_back(a);
  }
  for (int i = 0; i < (m); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    bs[a].push_back(b);
    bs[b].push_back(a);
  }
  init(0, n, 0);
  dfs1(0, -1);
  dfs2(0, -1);
  for (int i = 0; i < (n); ++i) {
    if (res[i]) --res[i];
    printf("%d ", res[i]);
  }
  return 0;
}

```