258_E. Little Elephant and Tree_36710
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 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 86;
vector<int> e[MAXN];
vector<pair<int, int> > s[MAXN];
int l[MAXN], r[MAXN];
int t, c[MAXN];
int n, q;
struct seg_tree {
  int nz[MAXN << 2], x[MAXN << 2];
  void init() {
    memset(nz, 0, sizeof(nz));
    memset(x, 0, sizeof(x));
  }
  void update(int r, int L, int R) {
    if (x[r])
      nz[r] = R - L + 1;
    else if (L >= R)
      nz[r] = 0;
    else
      nz[r] = nz[((r) << 1)] + nz[(((r) << 1) ^ 1)];
  }
  void add(int r, int L, int R, const int a, const int b, const int off) {
    if (a <= L && R <= b) {
      x[r] += off;
      update(r, L, R);
      return;
    }
    int M = ((L) + (R)) >> 1;
    if (a <= M) add(((r) << 1), L, M, a, b, off);
    if (b > M) add((((r) << 1) ^ 1), M + 1, R, a, b, off);
    update(r, L, R);
  }
  int sum() { return max(0, nz[1] - 1); }
  void info(int r, int L, int R) {
    printf("%d [%d, %d] x: %d, nz: %d\n", r, L, R, x[r], nz[r]);
    if (L >= R) return;
    int M = ((L) + (R)) >> 1;
    info(((r) << 1), L, M);
    info((((r) << 1) ^ 1), M + 1, R);
  }
} T;
int dfs(int r, int p) {
  l[r] = ::r[r] = t;
  for (int i = 0; i < e[r].size(); ++i)
    if (e[r][i] != p) ++t, ::r[r] = max(::r[r], dfs(e[r][i], r));
  return ::r[r];
}
void gao(int r, int p) {
  for (int i = 0; i < s[r].size(); ++i)
    T.add(1, 0, n - 1, s[r][i].first, s[r][i].second, 1);
  c[r] = T.sum();
  for (int i = 0; i < e[r].size(); ++i)
    if (e[r][i] != p) gao(e[r][i], r);
  for (int i = 0; i < s[r].size(); ++i)
    T.add(1, 0, n - 1, s[r][i].first, s[r][i].second, -1);
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1, a, b; i < n; ++i) {
    scanf("%d%d", &a, &b), --a, --b;
    e[a].push_back(b), e[b].push_back(a);
  }
  dfs(0, -1);
  for (int a, b; q--;) {
    scanf("%d%d", &a, &b), --a, --b;
    s[a].push_back(make_pair((l[a]), (r[a]))),
        s[a].push_back(make_pair((l[b]), (r[b])));
    s[b].push_back(make_pair((l[a]), (r[a]))),
        s[b].push_back(make_pair((l[b]), (r[b])));
  }
  gao(0, -1);
  for (int i = 0; i < n; ++i) printf("%d%s", c[i], i == n - 1 ? "\n" : " ");
  return 0;
}

5 1
1 2
1 3
3 5
3 4
2 3
 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
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
4 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 3
2 3
2 4
1 5
7 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
4 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
3 9
3 9
2 8
 11 3
1 3
2 3
2 4
1 5
4 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
4 9
3 9
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
1 8
 5 1
1 2
1 3
3 5
3 4
2 1
 11 3
1 3
2 3
2 4
1 8
7 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 2
2 3
3 4
1 5
5 6
4 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8
 11 3
1 3
2 3
2 4
1 8
7 6
5 7
5 8
6 9
8 10
8 11
3 9
5 6
2 8
 5 1
1 2
1 3
3 5
5 4
2 3
 11 3
1 2
2 3
2 4
1 10
5 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 3
2 3
2 4
1 5
4 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
3 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
4 11
3 6
2 2
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
5 10
8 11
4 9
3 6
2 8
 11 3
1 4
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
8 7
5 8
6 9
8 10
8 11
3 9
3 9
2 8
 11 3
1 2
2 3
3 4
2 5
5 6
4 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 8
5 6
5 7
5 8
6 9
8 10
8 11
4 11
3 9
2 4
 5 1
1 2
1 3
3 5
3 4
2 4
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
3 7
3 6
2 8
 11 3
1 3
2 3
2 4
1 5
7 6
5 7
5 8
6 9
8 10
8 11
3 9
5 6
2 8
 11 3
1 2
2 3
2 4
1 5
7 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
4 11
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
7 6
5 7
5 8
6 9
8 10
8 11
3 9
1 6
2 8
 11 3
1 2
2 3
2 4
1 10
5 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 1
 11 3
1 3
2 3
2 4
1 5
4 6
5 7
5 8
6 9
8 10
8 11
3 9
6 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
7 8
6 9
8 10
8 11
4 9
3 9
2 8
 11 3
1 3
2 3
2 4
1 8
7 6
5 7
5 11
6 9
8 10
8 11
3 9
5 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
4 11
3 6
2 4
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
4 8
6 9
8 10
8 11
4 11
3 6
2 2
 11 3
1 2
2 3
2 4
1 5
5 6
8 7
5 8
6 9
11 10
8 11
3 9
3 9
2 8
 11 3
1 2
2 3
2 4
1 5
8 6
5 7
7 8
6 9
8 10
8 11
4 9
3 9
2 8
 11 3
1 2
2 3
2 4
1 8
5 6
5 7
5 8
6 9
8 10
8 11
4 11
3 6
2 4
 11 3
1 3
2 3
2 4
1 5
7 6
5 7
5 8
6 9
8 10
8 11
3 9
1 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
1 7
5 8
6 9
8 10
8 11
3 9
3 6
1 8
 5 1
1 2
1 3
2 5
5 4
2 3

0 3 3 3 3 
 0 6 7 6 0 2 0 5 4 5 5 
 0 5 7 6 0 2 0 5 3 5 5  0 5 7 5 0 2 0 5 2 5 5  0 7 4 7 0 4 0 4 4 4 4  0 7 8 7 0 2 7 6 5 6 6  0 5 6 5 0 0 0 5 1 5 5  0 7 4 7 0 7 0 6 7 6 6  0 5 6 6 0 0 0 5 2 5 5  10 10 10 10 10 10 10 10 10 10 10  4 4 4 4 4  0 9 4 9 8 9 8 8 9 8 8  0 7 8 8 0 4 8 6 5 6 6  0 9 3 9 8 8 8 8 9 8 8  0 3 3 3 3  0 8 8 8 8 8 8 8 8 0 8  0 7 7 7 0 7 0 7 7 7 7  0 2 4 3 0 2 0 0 2 0 1  0 4 6 5 0 2 0 4 3 0 4  0 4 6 0 0 2 0 4 2 4 4  0 6 7 6 0 0 6 6 1 6 6  0 9 9 9 9 9 9 9 9 9 9  0 2 3 3 0 0 0 0 1 0 1  0 1 0 1 0  0 5 8 5 0 2 1 5 2 5 5  0 6 3 6 6 6 6 8 9 8 8  0 5 7 5 0 2 0 5 2 5 5  0 5 7 5 0 2 0 5 2 5 5  10 10 10 10 10 10 10 10 10 10 10  10 10 10 10 10 10 10 10 10 10 10  0 7 4 7 0 7 0 6 7 6 6  0 5 6 6 0 0 0 5 2 5 5  0 9 3 9 8 8 8 8 9 8 8  0 2 4 3 0 2 0 0 2 0 1  0 5 7 5 0 2 0 5 2 5 5  0 6 7 6 0 0 6 6 1 6 6  0 7 7 7 0 7 0 7 7 7 7  0 2 4 3 0 2 0 0 2 0 1  10 10 10 10 10 10 10 10 10 10 10  10 10 10 10 10 10 10 10 10 10 10  0 3 3 3 3 