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;
vector<int> g[100100], q[100100], d[100100];
int n, m, t = 1, l[100100], r[100100], c[100100];
int add[4 * 100100], tree[4 * 100100];
bool u[100100];
int get(int v, int l, int r) {
  if (add[v] > 0) return r - l + 1;
  return tree[v];
}
void fuck(int v, int l, int r) {
  if (add[v] == 0)
    if (l == r)
      tree[v] = 0;
    else {
      int m = (l + r) / 2;
      tree[v] = get(2 * v, l, m) + get(2 * v + 1, m + 1, r);
    }
}
int get(int v, int l, int r, int le, int re) {
  if (add[v] > 0) return re - le + 1;
  if (le == l && r == re) return get(v, l, r);
  int m = (l + r) / 2;
  if (re <= m) return get(2 * v, l, m, le, re);
  if (m + 1 <= le) return get(2 * v + 1, m + 1, r, le, re);
  return get(2 * v, l, m, le, m) + get(2 * v + 1, m + 1, r, m + 1, re);
}
void push(int v, int l, int r, int le, int re, int val) {
  if (le == l && r == re) {
    add[v] += val;
    fuck(v, l, r);
    return;
  }
  int m = (l + r) / 2;
  if (re <= m) push(2 * v, l, m, le, re, val);
  if (m + 1 <= le) push(2 * v + 1, m + 1, r, le, re, val);
  if (le <= m && m + 1 <= re) {
    push(2 * v, l, m, le, m, val);
    push(2 * v + 1, m + 1, r, m + 1, re, val);
  }
  fuck(v, l, r);
}
void read(void) {
  cin >> n >> m;
  for (int i = 1, a, b; i < n; ++i) {
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
}
void dfs(int v) {
  u[v] = 1;
  l[v] = t++;
  for (int i = 0; i < (int)g[v].size(); ++i) {
    int to = g[v][i];
    if (!u[to]) dfs(to), d[v].push_back(to);
  }
  r[v] = t - 1;
}
void store(void) {
  for (int i = 0, a, b; i < m; ++i) {
    cin >> a >> b;
    q[a].push_back(b);
    q[b].push_back(a);
  }
}
void run(int v) {
  for (int i = 0; i < (int)q[v].size(); ++i) {
    int to = q[v][i];
    push(1, 1, n, l[v], r[v], 1);
    push(1, 1, n, l[to], r[to], 1);
  }
  c[v] = get(1, 1, n, 1, n) - 1;
  if (c[v] == -1) c[v] = 0;
  for (int i = 0; i < (int)d[v].size(); ++i) {
    int to = d[v][i];
    run(to);
  }
  for (int i = 0; i < (int)q[v].size(); ++i) {
    int to = q[v][i];
    push(1, 1, n, l[v], r[v], -1);
    push(1, 1, n, l[to], r[to], -1);
  }
}
void test(void) {
  int t;
  cin >> t >> n;
  for (int i = 0, a, b, c, v; i < t; ++i) {
    cin >> c >> a >> b >> v;
    if (c == 1)
      push(1, 1, n, a, b, v);
    else
      cout << get(1, 1, n, a, b) << "\n";
  }
}
int main() {
  read();
  dfs(1);
  store();
  run(1);
  for (int i = 1; i <= n; ++i, cout << " ") cout << c[i];
}
