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;
constexpr int N = 1e5 + 10;
int n, open[N], close[N], mytime, ans[N], cnt[N], m, u, v, lazy[4 * N];
pair<int, int> tree[4 * N];
vector<int> node[N];
stack<int> s[N], st;
bool mark[N];
void build(int b, int e, int idx) {
  if (b + 1 == e) {
    tree[idx].second = 1;
    return;
  }
  int mid = (b + e) >> 1, lidx = idx << 1, ridx = lidx | 1;
  build(b, mid, lidx);
  build(mid, e, ridx);
  tree[idx].second = tree[lidx].second + tree[ridx].second;
}
void update(int b, int e, int l, int r, int val, int idx) {
  if (b >= r || e <= l) return;
  if (b >= l && e <= r) {
    lazy[idx] += val;
    tree[idx].first += val;
    return;
  }
  int mid = (b + e) >> 1, lidx = idx << 1, ridx = lidx | 1;
  update(b, mid, l, r, val, lidx);
  update(mid, e, l, r, val, ridx);
  if (tree[lidx].first == tree[ridx].first)
    tree[idx] = {tree[lidx].first, tree[ridx].second + tree[lidx].second};
  else if (tree[lidx].first < tree[ridx].first)
    tree[idx] = tree[lidx];
  else
    tree[idx] = tree[ridx];
  tree[idx].first += lazy[idx];
}
pair<int, int> query(int b, int e, int l, int r, int idx) {
  if (b >= r || e <= l) return {N * 10, N * 10};
  if (b >= l && e <= r) return {tree[idx].first, tree[idx].second};
  int mid = (b + e) >> 1, lidx = idx << 1, ridx = lidx | 1;
  pair<int, int> lchild = query(b, mid, l, r, lidx),
                 rchild = query(mid, e, l, r, ridx);
  if (lchild.first == rchild.first)
    return {lchild.first + lazy[idx], lchild.second + rchild.second};
  else if (lchild.first < rchild.first)
    return {lchild.first + lazy[idx], lchild.second};
  return {rchild.first + lazy[idx], rchild.second};
}
void dfs(int v) {
  mark[v] = true;
  open[v] = mytime++;
  for (auto i : node[v])
    if (!mark[i]) dfs(i);
  close[v] = mytime;
}
void func(int v) {
  mark[v] = true;
  while (!s[v].empty()) {
    st.push(s[v].top());
    update(0, n, open[v], close[v], 1, 1);
    update(0, n, open[s[v].top()], close[s[v].top()], 1, 1);
    s[v].pop();
  }
  pair<int, int> a1 = query(0, n, 0, open[v], 1),
                 a2 = query(0, n, open[v] + 1, n, 1);
  ans[v] = n - 1;
  if (!a1.first) ans[v] -= a1.second;
  if (!a2.first) ans[v] -= a2.second;
  for (auto i : node[v])
    if (!mark[i]) func(i);
  while (cnt[v]--) {
    update(0, n, open[v], close[v], -1, 1);
    update(0, n, open[st.top()], close[st.top()], -1, 1);
    st.pop();
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i < n; i++) {
    cin >> u >> v;
    node[v].push_back(u);
    node[u].push_back(v);
  }
  build(0, n, 1);
  dfs(1);
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    s[u].push(v);
    s[v].push(u);
    cnt[v]++;
    cnt[u]++;
  }
  memset(mark, 0, sizeof(mark));
  func(1);
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
  cout << '\n';
  return 0;
}
