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> ed[100005];
vector<pair<int, int> > e[100005];
int a[100005 * 4], c[100005 * 4], d[100005], L[100005], R[100005], ans[100005],
    n, m, x, y, len, v;
void dfs(int x, int last) {
  d[++len] = x, L[x] = len;
  for (int y : ed[x])
    if (y - last) dfs(y, x);
  R[x] = len;
}
void build(int t, int l, int r) {
  a[t] = r - l + 1;
  if (l == r) return;
  int mid = (l + r) / 2;
  build(t * 2, l, mid), build(t * 2 + 1, mid + 1, r);
}
void add(int t, int l, int r, int ll, int rr) {
  if (l == ll && r == rr) {
    c[t] += v, a[t] = c[t] ? 0 : r - l ? a[t * 2] + a[t * 2 + 1] : 1;
    return;
  }
  int mid = (l + r) / 2;
  if (rr <= mid)
    add(t * 2, l, mid, ll, rr);
  else if (ll > mid)
    add(t * 2 + 1, mid + 1, r, ll, rr);
  else
    add(t * 2, l, mid, ll, mid), add(t * 2 + 1, mid + 1, r, mid + 1, rr);
  a[t] = c[t] ? 0 : a[t * 2] + a[t * 2 + 1];
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i < n; i++)
    scanf("%d%d", &x, &y), ed[x].push_back(y), ed[y].push_back(x);
  dfs(1, 0);
  build(1, 1, n);
  for (int i = 1; i <= m; i++)
    scanf("%d%d", &x, &y), e[L[x]].push_back(make_pair(x, y)),
        e[R[x] + 1].push_back(make_pair(x, -y)),
        e[L[y]].push_back(make_pair(x, y)),
        e[R[y] + 1].push_back(make_pair(x, -y));
  for (int i = 1; i <= n; i++) {
    for (pair<int, int> j : e[i]) {
      v = 1;
      if (j.second < 0) j.second *= -1, v = -1;
      add(1, 1, n, L[j.first], R[j.first]),
          add(1, 1, n, L[j.second], R[j.second]);
    }
    v = 1, add(1, 1, n, i, i), ans[d[i]] += n - a[1] - 1, v = -1,
    add(1, 1, n, i, i);
  }
  for (int i = 1; i <= n; i++) printf("%d%s", ans[i], i < n ? " " : "\n");
  return 0;
}
