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;
int n, m, i, j, l[100005], r[100005], nxt, lx, ly, lval, ans[100005];
vector<int> edge[100005], q[100005];
struct node {
  int mn, cnt, nz, tag;
} tree[400005];
void pre(int id, int p) {
  l[id] = ++nxt;
  for (int k = 0; k < edge[id].size(); k++) {
    int to = edge[id][k];
    if (to == p) continue;
    pre(to, id);
  }
  r[id] = nxt;
}
void pushup(int ind, int l, int r) {
  if (tree[ind * 2].mn < tree[ind * 2 + 1].mn) {
    tree[ind].mn = tree[ind * 2].mn;
    tree[ind].cnt = tree[ind * 2].cnt;
  } else if (tree[ind * 2].mn > tree[ind * 2 + 1].mn) {
    tree[ind].mn = tree[ind * 2 + 1].mn;
    tree[ind].cnt = tree[ind * 2 + 1].cnt;
  } else {
    tree[ind].mn = tree[ind * 2].mn;
    tree[ind].cnt = tree[ind * 2].cnt + tree[ind * 2 + 1].cnt;
  }
  tree[ind].nz = tree[ind * 2].nz + tree[ind * 2 + 1].nz;
}
void build(int l, int r, int ind) {
  if (l == r) {
    tree[ind].mn = 0;
    tree[ind].cnt = 1;
    tree[ind].nz = 0;
    tree[ind].tag = 0;
    return;
  }
  int mid = (l + r) / 2;
  build(l, mid, ind * 2);
  build(mid + 1, r, ind * 2 + 1);
  pushup(ind, l, r);
}
void pushdw(int ind, int l, int r) {
  int tmp = tree[ind].tag;
  tree[ind].tag = 0;
  tree[ind * 2].mn += tmp;
  tree[ind * 2 + 1].mn += tmp;
  tree[ind * 2].tag += tmp;
  tree[ind * 2 + 1].tag += tmp;
  int mid = (l + r) / 2;
  if (tree[ind * 2].mn == 0)
    tree[ind * 2].nz = (mid - l + 1) - tree[ind * 2].cnt;
  else
    tree[ind * 2].nz = mid - l + 1;
  if (tree[ind * 2 + 1].mn == 0)
    tree[ind * 2 + 1].nz = (r - (mid + 1) + 1) - tree[ind * 2 + 1].cnt;
  else
    tree[ind * 2 + 1].nz = r - (mid + 1) + 1;
}
void update(int l, int r, int ind) {
  if (lx <= l && r <= ly) {
    tree[ind].mn += lval;
    tree[ind].tag += lval;
    if (tree[ind].mn == 0)
      tree[ind].nz = (r - l + 1) - tree[ind].cnt;
    else
      tree[ind].nz = r - l + 1;
    return;
  }
  pushdw(ind, l, r);
  int mid = (l + r) / 2;
  if (lx <= mid) update(l, mid, ind * 2);
  if (ly > mid) update(mid + 1, r, ind * 2 + 1);
  pushup(ind, l, r);
}
void solve(int id, int p) {
  for (int k = 0; k < q[id].size(); k++) {
    int to = q[id][k];
    lx = l[to];
    ly = r[to];
    lval = 1;
    update(1, n, 1);
  }
  ans[id] = tree[1].nz;
  ans[id] = max(0, ans[id] - 1);
  for (int k = 0; k < edge[id].size(); k++) {
    int to = edge[id][k];
    if (to == p) continue;
    solve(to, id);
  }
  for (int k = 0; k < q[id].size(); k++) {
    int to = q[id][k];
    lx = l[to];
    ly = r[to];
    lval = -1;
    update(1, n, 1);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (i = 0; i < n - 1; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    edge[x].push_back(y);
    edge[y].push_back(x);
  }
  pre(1, -1);
  for (i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    q[x].push_back(x);
    q[x].push_back(y);
    q[y].push_back(x);
    q[y].push_back(y);
  }
  build(1, n, 1);
  solve(1, -1);
  for (i = 1; i <= n; i++) {
    if (i == 1)
      printf("%d", ans[i]);
    else
      printf(" %d", ans[i]);
  }
  printf("\n");
}
