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 = 100100;
vector<int> ve[MAXN];
int l[MAXN], r[MAXN], res[MAXN], cur = 0;
void dfs(int v, int par) {
  for (__typeof((ve[v]).begin()) it = (ve[v]).begin(); it != (ve[v]).end();
       ++it) {
    if (*it == par) {
      swap(ve[v].back(), *it);
      ve[v].pop_back();
      break;
    }
  }
  l[v] = r[v] = cur++;
  for (__typeof((ve[v]).begin()) it = (ve[v]).begin(); it != (ve[v]).end();
       ++it) {
    dfs(*it, v);
    r[v] = r[*it];
  }
}
struct event {
  int x, y1, y2, m;
  event(int _x = 0, int _y1 = 0, int _y2 = 0, int _m = 0)
      : x(_x), y1(_y1), y2(_y2), m(_m) {}
  bool operator<(const event &e) const {
    if (x == e.x) {
      return m > e.m;
    }
    return x < e.x;
  }
};
int cnt[1 << 18], sum[1 << 18], BASE;
void akt(int p, int x, int y) {
  if (cnt[p] > 0) {
    sum[p] = y - x + 1;
  } else {
    sum[p] = (p >= BASE ? 0 : sum[2 * p] + sum[2 * p + 1]);
  }
}
void add(int a, int b, int x, int y, int p, int v) {
  if (a == x && b == y) {
    cnt[p] += v;
    akt(p, x, y);
    return;
  }
  int mid = (x + y) / 2;
  if (b <= mid) {
    add(a, b, x, mid, 2 * p, v);
  } else if (a > mid) {
    add(a, b, mid + 1, y, 2 * p + 1, v);
  } else {
    add(a, mid, x, mid, 2 * p, v);
    add(mid + 1, b, mid + 1, y, 2 * p + 1, v);
  }
  akt(p, x, y);
}
int main(void) {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < (n - 1); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    ve[a].push_back(b);
    ve[b].push_back(a);
  }
  dfs(0, -1);
  for (BASE = 1; BASE < n; BASE <<= 1)
    ;
  vector<event> E;
  for (int i = 0; i < (n); ++i) {
    E.push_back(event(i, 0, 0, 0));
  }
  for (int i = 0; i < (m); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    if (l[a] > l[b]) {
      swap(a, b);
    }
    if (l[b] <= r[a]) {
      E.push_back(event(l[a], l[a], r[a], 1));
      E.push_back(event(r[a], l[a], r[a], -1));
    } else {
      E.push_back(event(l[a], l[a], r[a], 1));
      E.push_back(event(r[a], l[a], r[a], -1));
      E.push_back(event(l[a], l[b], r[b], 1));
      E.push_back(event(r[a], l[b], r[b], -1));
      E.push_back(event(l[b], l[a], r[a], 1));
      E.push_back(event(r[b], l[a], r[a], -1));
      E.push_back(event(l[b], l[b], r[b], 1));
      E.push_back(event(r[b], l[b], r[b], -1));
    }
  }
  sort((E).begin(), (E).end());
  for (__typeof((E).begin()) it = (E).begin(); it != (E).end(); ++it) {
    const event &e = *it;
    if (it->m == 0) {
      res[it->x] = sum[1];
    } else {
      assert(e.y1 <= e.y2);
      add(e.y1, e.y2, 0, BASE - 1, 1, e.m);
    }
  }
  for (int i = 0; i < (n); ++i) {
    if (res[l[i]] > 0) {
      --res[l[i]];
    }
    printf("%d ", res[l[i]]);
  }
  puts("");
  return 0;
}
