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 sum[666666];
int cover[666666];
int seg_modify(int l, int r, int delta, int tl, int tr, int t = 1) {
  if (l <= tl && tr <= r) {
    sum[t] += delta;
    cover[t] = sum[t] ? tr - tl + 1 : cover[t * 2] + cover[t * 2 + 1];
    return 0;
  }
  int mid = (tl + tr) / 2;
  if (l <= mid) seg_modify(l, r, delta, tl, mid, t * 2);
  if (r > mid) seg_modify(l, r, delta, mid + 1, tr, t * 2 + 1);
  cover[t] = sum[t] ? tr - tl + 1 : cover[t * 2] + cover[t * 2 + 1];
  return 0;
}
int seg_query() { return cover[1]; }
vector<int> edges[111111];
vector<int> query[111111];
int ans[111111];
int oin[111111];
int oout[111111];
int idx = 0;
int dorder(int x, int fa = -1) {
  oin[x] = ++idx;
  for (vector<int>::iterator it = edges[x].begin(); it != edges[x].end();
       ++it) {
    if (*it == fa) continue;
    dorder(*it, x);
  }
  oout[x] = idx;
  return 0;
}
int n = 0;
int dfs(int x, int fa = -1) {
  if (query[x].size()) {
    seg_modify(oin[x], oout[x], 1, 1, n);
  }
  for (vector<int>::iterator it = query[x].begin(); it != query[x].end(); ++it)
    seg_modify(oin[*it], oout[*it], 1, 1, n);
  ans[x] = seg_query();
  for (vector<int>::iterator it = edges[x].begin(); it != edges[x].end();
       ++it) {
    if (*it == fa) continue;
    dfs(*it, x);
  }
  for (vector<int>::iterator it = query[x].begin(); it != query[x].end(); ++it)
    seg_modify(oin[*it], oout[*it], -1, 1, n);
  if (query[x].size()) seg_modify(oin[x], oout[x], -1, 1, n);
  return 0;
}
int main(void) {
  int m = 0;
  scanf("%d %d", &n, &m);
  for (int i = 1; i < n; i++) {
    int x = 0;
    int y = 0;
    scanf("%d %d", &x, &y);
    edges[x].push_back(y);
    edges[y].push_back(x);
  }
  for (int i = 0; i < m; i++) {
    int x = 0;
    int y = 0;
    scanf("%d %d", &x, &y);
    query[x].push_back(y);
    query[y].push_back(x);
  }
  dorder(1);
  dfs(1);
  for (int i = 1; i <= n; i++)
    printf("%d%c", ans[i] > 0 ? ans[i] - 1 : 0, i == n ? '\n' : ' ');
  while (getchar() != EOF)
    ;
  return 0;
}
