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>
struct Star {
  int v[(100001 * 2)], pre[(100001 * 2)], ind[100001], n;
  void make_edge(int ui, int vi) {
    int id = ++n;
    v[id] = vi;
    pre[id] = ind[ui];
    ind[ui] = id;
  }
} G;
int N, Q, inp[100001], oup[100001], _inp[(100001 * 2)], tim, ans[100001];
bool vis[100001];
void dfs(int n) {
  if (vis[n]) return;
  vis[n] = true;
  inp[n] = ++tim;
  _inp[tim] = n;
  int m, mid;
  for (mid = G.ind[n]; mid; mid = G.pre[mid]) {
    m = G.v[mid];
    dfs(m);
  }
  oup[n] = ++tim;
}
struct Node {
  int n, m, cover;
  void print() { printf("(%d/%d) cover=%d\n", m, n, cover); }
} node[(100001 * 2) * 3];
int TM, TN;
void upper(int id) {
  if (node[id].cover == 0) {
    if (id >= TM)
      node[id].m = 0;
    else
      node[id].m = node[id << 1].m + node[id << 1 | 1].m;
  } else
    node[id].m = node[id].n;
}
void cng(int id, int v) {
  node[id].cover += v;
  upper(id);
}
void modify(int x, int y, int c) {
  int i, j;
  for (i = x + TM - 1, j = y + TM + 1; i ^ j ^ 1; i >>= 1, j >>= 1) {
    if (~i & 1) cng(i ^ 1, c);
    if (j & 1) cng(j ^ 1, c);
    upper(i);
    upper(j);
  }
  upper(j);
  for (; i; i >>= 1) {
    upper(i);
  }
}
struct Cover {
  int p, q, id;
  Cover() {}
  Cover(int pi, int qi, int oi) { p = pi, q = qi, id = oi; }
  bool operator<(const Cover &B) const {
    return (p == B.p) ? (q > B.q) : (p < B.p);
  }
} cover[(100001 * 2)];
int ent[100001][2], stk[(100001 * 2)], sn;
void coveron(int eid, int v) {
  int a = ent[eid][0], b = ent[eid][1];
  modify(inp[a], oup[a], v);
  modify(inp[b], oup[b], v);
}
void print(int eid) {
  int a = ent[eid][0], b = ent[eid][1];
  printf("[%d,%d] [%d,%d]\n", inp[a], oup[a], inp[b], oup[b]);
}
int main() {
  int i, j, x, y;
  scanf("%d%d", &N, &Q);
  for (i = 1; i < N; i++) {
    scanf("%d%d", &x, &y);
    G.make_edge(x, y);
    G.make_edge(y, x);
  }
  dfs(1);
  TN = N * 2;
  for (TM = 1; TM < TN + 2; TM <<= 1)
    ;
  for (i = 1; i <= N; i++) node[inp[i] + TM].n = 1;
  for (i = TM - 1; i > 0; i--) node[i].n = node[i << 1].n + node[i << 1 | 1].n;
  for (i = 1; i <= Q; i++) {
    scanf("%d%d", &x, &y);
    ent[i][0] = x, ent[i][1] = y;
    cover[(i << 1)] = Cover(inp[x], oup[x], i);
    cover[(i << 1) - 1] = Cover(inp[y], oup[y], i);
  }
  std::sort(cover + 1, cover + Q * 2 + 1);
  for (i = 1, j = 1; i <= TN; i++) {
    while (j <= 2 * Q && cover[j].p == i) {
      stk[sn++] = j;
      coveron(cover[j].id, 1);
      j++;
    }
    while (sn > 0 && cover[stk[sn - 1]].q == i) {
      coveron(cover[stk[sn - 1]].id, -1);
      sn--;
    }
    if (_inp[i]) {
      ans[_inp[i]] = node[1].m - 1;
      if (sn == 0) ans[_inp[i]] = 0;
    }
  }
  for (i = 1; i <= N; i++) {
    if (i > 1) putchar(' ');
    printf("%d", ans[i]);
  }
  putchar('\n');
}
