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;
template <class T>
struct splnode {
  splnode() : P(NULL) {
    C[0] = C[1] = NULL;
    fix();
  }
  T V;
  splnode* P;
  splnode<T>* C[2];
  void fix() {
    if (C[0]) C[0]->P = this;
    if (C[1]) C[1]->P = this;
    V.fix(this);
  }
  void push() { V.push(this); }
  int up(splnode<T>* stopp = NULL) {
    return !P || P == stopp ? -1 : (P->C[0] == this ? 0 : 1);
  }
  splnode<T>* splay(splnode<T>* stopp = NULL) {
    for (int c1 = up(stopp); c1 != -1; c1 = up(stopp)) {
      int c2 = P->up(stopp);
      if (c2 == -1) {
        P->zig(c1);
      } else if (c1 == c2) {
        P->P->zig(c1);
        P->zig(c1);
      } else {
        P->zig(c1);
        P->zig(c2);
      }
    }
    if (P) P->fix();
    push();
    return this;
  }

 private:
  void zig(int c) {
    splnode<T>* X = C[c];
    push();
    X->push();
    if (X->P = P) P->C[up()] = X;
    C[c] = X->C[1 - c];
    X->C[1 - c] = this;
    fix();
    X->fix();
  }
};
template <class T>
splnode<T>* spl_extreme(splnode<T>* x, int c) {
  splnode<T>* y;
  for (y = x; y->C[c]; y = y->C[c])
    ;
  return y->splay(x->P);
}
template <class T>
splnode<T>* spl_subtree(splnode<T>* x, splnode<T>* y) {
  if (!x) {
    y->splay();
    return y->C[0] ? spl_extreme(y->C[0], 1)->splay()->C[1] : y;
  } else if (!y) {
    x->splay();
    return x->C[1] ? spl_extreme(x->C[1], 0)->splay()->C[0] : x;
  }
  x->splay();
  y->splay(x);
  int c = x == y ? 1 : y->up();
  if (c == -1) return NULL;
  c = 1 - c;
  splnode<T>* lft = x->C[c] ? spl_extreme(x->C[c], 1 - c) : NULL;
  splnode<T>* rht = y->C[1 - c] ? spl_extreme(y->C[1 - c], c) : NULL;
  if (lft) lft->splay();
  if (rht) rht->splay(lft);
  return rht ? y : x;
}
struct node {
  int add;
  int val;
  int min_val;
  int min_cnt;
  node() : add(0), val(0), min_val(0), min_cnt(0) {}
  void fix(splnode<node>* x) {
    min_val = val;
    min_cnt = 1;
    for (int i = 0; i < 2; i++) {
      if (!x->C[i]) continue;
      int val = x->C[i]->V.min_val + x->C[i]->V.add;
      if (val == min_val) {
        min_cnt += x->C[i]->V.min_cnt;
      } else if (val < min_val) {
        min_val = val;
        min_cnt = x->C[i]->V.min_cnt;
      }
    }
  }
  void push(splnode<node>* x) {
    val += add;
    min_val += add;
    if (x->C[0]) x->C[0]->V.add += add;
    if (x->C[1]) x->C[1]->V.add += add;
    add = 0;
  }
};
int V[100010];
int L[100010];
int R[100010];
splnode<node> nds[100010];
vector<pair<int, int> > rngs[100010];
vector<int> E[100010];
void dfs(int x, int p, int& ind) {
  L[x] = ind++;
  for (int i = 0; i < E[x].size(); i++) {
    int u = E[x][i];
    if (u != p) {
      dfs(u, x, ind);
    }
  }
  R[x] = ind;
}
void search(int x, int p) {
  for (int i = 0; i < rngs[x].size(); i++) {
    splnode<node>* nd =
        spl_subtree(&nds[rngs[x][i].first], &nds[rngs[x][i].second]);
    nd->V.add++;
    nd->splay();
  }
  nds[x].splay();
  V[x] = nds[x].V.min_val == 0 ? nds[x].V.min_cnt : 0;
  for (int i = 0; i < E[x].size(); i++) {
    if (E[x][i] != p) {
      search(E[x][i], x);
    }
  }
  for (int i = 0; i < rngs[x].size(); i++) {
    splnode<node>* nd =
        spl_subtree(&nds[rngs[x][i].first], &nds[rngs[x][i].second]);
    nd->V.add--;
    nd->splay();
  }
}
int main() {
  int N, M;
  cin >> N >> M;
  for (int i = 1; i < N; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  int ind = 0;
  dfs(0, -1, ind);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    rngs[a].push_back(make_pair(L[a], R[a] - 1));
    rngs[a].push_back(make_pair(L[b], R[b] - 1));
    rngs[b].push_back(make_pair(L[a], R[a] - 1));
    rngs[b].push_back(make_pair(L[b], R[b] - 1));
  }
  for (int i = 0; i + 1 < N; i++) nds[i].C[1] = &nds[i + 1];
  for (int i = N - 1; i >= 0; i--) nds[i].fix();
  search(0, -1);
  for (int i = 0; i < N; i++) {
    V[i] = N - V[i];
    if (V[i]) V[i]--;
    if (i) cout << ' ';
    cout << V[i];
  }
  cout << endl;
}
