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;
vector<int> graph[100010];
vector<int> connect[100010];
struct node {
  int min, add, cnt;
};
node tree[2 * (1 << 18)];
void init(void) {
  int i;
  for ((i) = 0; (i) < (int)(2 * (1 << 18)); (i)++)
    tree[i].min = tree[i].add = 0;
  for (i = (1 << 18); i < 2 * (1 << 18); i++) tree[i].cnt = 1;
  for (i = (1 << 18) - 1; i >= 1; i--)
    tree[i].cnt = tree[2 * i].cnt + tree[2 * i + 1].cnt;
}
void update(int id) {
  int L = tree[2 * id].min + tree[2 * id].add;
  int R = tree[2 * id + 1].min + tree[2 * id + 1].add;
  int small = min(L, R);
  tree[id].min = small;
  tree[id].add = 0;
  tree[id].cnt = ((L == small) ? tree[2 * id].cnt : 0) +
                 ((R == small) ? tree[2 * id + 1].cnt : 0);
}
void plus_query(int L, int R, int id = 1, int low = 0, int high = (1 << 18)) {
  if (L <= low && R >= high) {
    tree[id].add++;
    return;
  }
  int mid = (low + high) / 2;
  if (tree[id].add != 0) {
    int tmp = tree[id].add;
    tree[id].min += tmp;
    tree[2 * id].add += tmp;
    tree[2 * id + 1].add += tmp;
    tree[id].add = 0;
  }
  if (L < mid) plus_query(L, R, 2 * id, low, mid);
  if (R > mid) plus_query(L, R, 2 * id + 1, mid, high);
  update(id);
}
void minus_query(int L, int R, int id = 1, int low = 0, int high = (1 << 18)) {
  if (L <= low && R >= high) {
    tree[id].add--;
    return;
  }
  int mid = (low + high) / 2;
  if (tree[id].add != 0) {
    int tmp = tree[id].add;
    tree[id].min += tmp;
    tree[2 * id].add += tmp;
    tree[2 * id + 1].add += tmp;
    tree[id].add = 0;
  }
  if (L < mid) minus_query(L, R, 2 * id, low, mid);
  if (R > mid) minus_query(L, R, 2 * id + 1, mid, high);
  update(id);
}
int nonzero_query(void) {
  if (tree[1].min + tree[1].add != 0) return (1 << 18);
  return (1 << 18) - tree[1].cnt;
}
int X;
int L[100010], R[100010];
int ans[100010];
void dfs(int p, int x) {
  int i;
  for ((i) = 0; (i) < (int)(connect[x].size()); (i)++) {
    int y = connect[x][i];
    plus_query(L[y], R[y] + 1);
  }
  ans[x] = nonzero_query() / 2;
  if (ans[x] > 0) ans[x]--;
  for ((i) = 0; (i) < (int)(graph[x].size()); (i)++) {
    int y = graph[x][i];
    if (y != p) dfs(x, y);
  }
  for ((i) = 0; (i) < (int)(connect[x].size()); (i)++) {
    int y = connect[x][i];
    minus_query(L[y], R[y] + 1);
  }
}
void make_euler(int p, int x) {
  L[x] = X;
  X++;
  int i;
  for ((i) = 0; (i) < (int)(graph[x].size()); (i)++) {
    int y = graph[x][i];
    if (y != p) make_euler(x, y);
  }
  R[x] = X;
  X++;
}
int main(void) {
  int Q, a, b, i;
  cin >> N >> Q;
  for ((i) = 0; (i) < (int)(N - 1); (i)++) {
    scanf("%d%d", &a, &b);
    a--;
    b--;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  for ((i) = 0; (i) < (int)(Q); (i)++) {
    scanf("%d%d", &a, &b);
    a--;
    b--;
    connect[a].push_back(a);
    connect[a].push_back(b);
    connect[b].push_back(a);
    connect[b].push_back(b);
  }
  init();
  make_euler(-1, 0);
  dfs(-1, 0);
  for ((i) = 0; (i) < (int)(N); (i)++) {
    printf("%d", ans[i]);
    if (i == N - 1)
      printf("\n");
    else
      printf(" ");
  }
  return 0;
}
