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>
int32_t *tin, *tout;
void dfs(int32_t vertex, int32_t parent, std::vector<int32_t>* tree,
         std::vector<int32_t>& euler) {
  tin[vertex] = euler.size();
  euler.push_back(vertex);
  for (int32_t i = 0; i < tree[vertex].size(); i++)
    if (tree[vertex][i] != parent) dfs(tree[vertex][i], vertex, tree, euler);
  tout[vertex] = euler.size();
}
struct Event {
  bool open;
  int32_t index;
  Event() {}
  Event(bool open_, int32_t index_) {
    open = open_;
    index = index_;
  }
};
std::pair<int32_t, int32_t>* segtree;
int32_t* lazy;
void build(int32_t node, int32_t left, int32_t right) {
  lazy[node] = 0;
  segtree[node] = {0, right - left};
  if (right - left == 1) {
    return;
  }
  int32_t m = (left + right) / 2;
  build(node * 2 + 1, left, m);
  build(node * 2 + 2, m, right);
}
void propagate(int32_t node) {
  segtree[node * 2 + 1].first += lazy[node];
  segtree[node * 2 + 2].first += lazy[node];
  lazy[node * 2 + 1] += lazy[node];
  lazy[node * 2 + 2] += lazy[node];
  lazy[node] = 0;
}
std::pair<int32_t, int32_t> combine(std::pair<int32_t, int32_t> p1,
                                    std::pair<int32_t, int32_t> p2) {
  if (p1.first < p2.first) return p1;
  if (p1.first > p2.first) return p2;
  return {p1.first, p1.second + p2.second};
}
void add_on_seg(int32_t node, int32_t left, int32_t right, int32_t query_left,
                int32_t query_right, int32_t d) {
  if (left >= query_right || right <= query_left) return;
  if (left >= query_left && right <= query_right) {
    segtree[node].first += d;
    lazy[node] += d;
    return;
  }
  propagate(node);
  int32_t m = (left + right) / 2;
  add_on_seg(node * 2 + 1, left, m, query_left, query_right, d);
  add_on_seg(node * 2 + 2, m, right, query_left, query_right, d);
  segtree[node] = combine(segtree[node * 2 + 1], segtree[node * 2 + 2]);
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int32_t n, m;
  std::cin >> n >> m;
  std::vector<int32_t>* tree = new std::vector<int32_t>[n];
  for (int32_t i = 0; i < n - 1; i++) {
    int32_t src, dst;
    std::cin >> src >> dst;
    src--;
    dst--;
    tree[src].push_back(dst);
    tree[dst].push_back(src);
  }
  std::vector<int32_t> euler;
  tin = new int32_t[n];
  tout = new int32_t[n];
  dfs(0, -1, tree, euler);
  std::pair<std::pair<int32_t, int32_t>, std::pair<int32_t, int32_t> >*
      segments = new std::pair<std::pair<int32_t, int32_t>,
                               std::pair<int32_t, int32_t> >[m];
  for (int32_t q = 0; q < m; q++) {
    int32_t v1, v2;
    std::cin >> v1 >> v2;
    v1--;
    v2--;
    segments[q] = {{tin[v1], tout[v1]}, {tin[v2], tout[v2]}};
  }
  std::vector<Event>* events = new std::vector<Event>[n + 1];
  for (int32_t i = 0; i < m; i++) {
    events[segments[i].first.first].emplace_back(true, i);
    events[segments[i].first.second].emplace_back(false, i);
    events[segments[i].second.first].emplace_back(true, i);
    events[segments[i].second.second].emplace_back(false, i);
  }
  int32_t* answer = new int32_t[n];
  segtree = new std::pair<int32_t, int32_t>[4 * n];
  lazy = new int32_t[4 * n];
  build(0, 0, n);
  for (int32_t i = 0; i < n; i++) {
    for (int32_t j = 0; j < events[i].size(); j++)
      if (events[i][j].open) {
        add_on_seg(0, 0, n, segments[events[i][j].index].first.first,
                   segments[events[i][j].index].first.second, 1);
        add_on_seg(0, 0, n, segments[events[i][j].index].second.first,
                   segments[events[i][j].index].second.second, 1);
      } else {
        add_on_seg(0, 0, n, segments[events[i][j].index].first.first,
                   segments[events[i][j].index].first.second, -1);
        add_on_seg(0, 0, n, segments[events[i][j].index].second.first,
                   segments[events[i][j].index].second.second, -1);
      }
    answer[euler[i]] =
        std::max(0, n - (segtree[0].first == 0 ? segtree[0].second : 0) - 1);
  }
  for (int32_t i = 0; i < n; i++) std::cout << answer[i] << " ";
  return 0;
}
