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;
class Rectangle {
 public:
  int x1, y1, x2, y2;
  static Rectangle empt;
  Rectangle() { x1 = y1 = x2 = y2 = 0; }
  Rectangle(int X1, int Y1, int X2, int Y2) {
    x1 = X1;
    y1 = Y1;
    x2 = X2;
    y2 = Y2;
  }
  Rectangle intersect(Rectangle R) {
    if (R.x1 > x2 || R.x2 < x1) return empt;
    if (R.y1 > y2 || R.y2 < y1) return empt;
    Rectangle ret =
        Rectangle(max(x1, R.x1), max(y1, R.y1), min(x2, R.x2), min(y2, R.y2));
    return ret;
  }
  bool operator==(Rectangle R) {
    return (R.x1 == x1) && (R.y1 == y1) && (R.y2 == y2) && (R.x2 == x2);
  }
};
struct Event {
  int x, y1, y2, type;
  Event() {}
  Event(int x, int y1, int y2, int type) : x(x), y1(y1), y2(y2), type(type) {}
};
bool operator<(const Event& A, const Event& B) {
  if (A.x != B.x)
    return A.x < B.x;
  else
    return A.type < B.type;
}
const int MX = (1 << 17);
struct Node {
  int prob, sum, ans;
  Node() {}
  Node(int prob, int sum, int ans) : prob(prob), sum(sum), ans(ans) {}
};
Node tree[MX * 4];
int interval[MX];
void build(int x, int a, int b) {
  tree[x] = Node(0, 0, 0);
  if (a == b) {
    tree[x].sum += interval[a];
    return;
  }
  build(x * 2, a, (a + b) / 2);
  build(x * 2 + 1, (a + b) / 2 + 1, b);
  tree[x].sum = tree[x * 2].sum + tree[x * 2 + 1].sum;
}
int ask(int x) {
  if (tree[x].prob) return tree[x].sum;
  return tree[x].ans;
}
int st, en, V;
void update(int x, int a, int b) {
  if (st > b || en < a) return;
  if (a >= st && b <= en) {
    tree[x].prob += V;
    return;
  }
  update(x * 2, a, (a + b) / 2);
  update(x * 2 + 1, (a + b) / 2 + 1, b);
  tree[x].ans = ask(x * 2) + ask(x * 2 + 1);
}
Rectangle Rectangle::empt = Rectangle();
vector<Rectangle> Rect;
vector<int> Start, End, sorted;
vector<Event> sweep;
int n;
void compressncalc() {
  sweep.clear();
  Start.clear();
  End.clear();
  sorted.clear();
  for (auto R : Rect) {
    sorted.push_back(R.y1);
    sorted.push_back(R.y2);
  }
  sort(sorted.begin(), sorted.end());
  sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
  int sz = sorted.size();
  for (int j = 0; j < sz; j++) {
    Start.push_back(sorted[j]);
    End.push_back(sorted[j]);
    if (j < sz - 1 && sorted[j] != sorted[j + 1] - 1) {
      Start.push_back(sorted[j] + 1);
      End.push_back(sorted[j + 1] - 1);
    }
  }
  sz = Start.size();
  for (int j = 0; j < sz; j++) interval[j + 1] = End[j] - Start[j] + 1;
  for (auto R : Rect) {
    sweep.push_back(Event(R.x1, R.y1, R.y2, 1));
    sweep.push_back(Event(R.x2 + 1, R.y1, R.y2, -1));
  }
  for (int j = 1; j <= n; j++) sweep.push_back(Event(j, 100, 100, 100));
  sort(sweep.begin(), sweep.end());
  build(1, 1, sz);
}
int ans[MX];
void Sweep() {
  if (sorted.empty() || sweep.empty()) return;
  int last = 0, sz_ = Start.size();
  for (int j = 0; j < sweep.size(); j++) {
    if (sweep[j].type == 100) {
      ans[sweep[j].x] = ask(1);
      continue;
    }
    last = sweep[j].x;
    V = sweep[j].type;
    st = lower_bound(Start.begin(), Start.end(), sweep[j].y1) - Start.begin() +
         1;
    en = lower_bound(End.begin(), End.end(), sweep[j].y2) - End.begin() + 1;
    update(1, 1, sz_);
  }
}
int in[MX], out[MX];
vector<int> v[MX];
int QN, timer;
void dfs(int x, int p) {
  in[x] = ++timer;
  for (auto nxt : v[x]) {
    if (nxt == p) continue;
    dfs(nxt, x);
  }
  out[x] = timer;
}
int main() {
  scanf("%d %d", &n, &QN);
  for (int j = 1; j < n; j++) {
    int a, b;
    scanf("%d %d", &a, &b);
    v[a].push_back(b);
    v[b].push_back(a);
  }
  dfs(1, -1);
  while (QN--) {
    int a, b;
    scanf("%d %d", &a, &b);
    int aa, bb, aaa, bbb;
    aa = in[a], aaa = out[a];
    bb = in[b], bbb = out[b];
    Rect.push_back(Rectangle(aa, bb, aaa, bbb));
    Rect.push_back(Rectangle(bb, aa, bbb, aaa));
    Rect.push_back(Rectangle(bb, bb, bbb, bbb));
    Rect.push_back(Rectangle(aa, aa, aaa, aaa));
  }
  compressncalc();
  Sweep();
  for (int j = 1; j <= n; j++) printf("%d ", max(0, ans[in[j]] - 1));
}
