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;
const int oo = 0x3f3f3f3f;
const double eps = 1e-9;
struct ENTRY {
  int todo;
  int v;
  ENTRY() : todo(0), v(0) {}
};
ENTRY segt_active[4 * (100 * 1024)];
ENTRY segt_cnt[4 * (100 * 1024)];
int segt_update(ENTRY *segt, int p, int i, int j, int a, int b, int v = 0) {
  if (b < i || j < a) return 0;
  if (a <= i && j <= b) {
    segt[p].todo += v;
    return segt[p].v + segt[p].todo * (j - i + 1);
  }
  int p1 = 2 * p + 1;
  int p2 = 2 * p + 2;
  segt[p1].todo += segt[p].todo;
  segt[p2].todo += segt[p].todo;
  segt[p].todo = 0;
  int ii = (i + j) / 2;
  int jj = ii + 1;
  int ret = segt_update(segt, p1, i, ii, a, b, v) +
            segt_update(segt, p2, jj, j, a, b, v);
  segt[p].v = segt[p1].v + segt[p1].todo * (ii - i + 1) + segt[p2].v +
              segt[p2].todo * (j - jj + 1);
  return ret;
}
int N, K;
vector<int> iadj[(100 * 1024)];
vector<int> adj[(100 * 1024)];
int cnt[(100 * 1024)];
int par[(100 * 1024)];
int new2orig[(100 * 1024)];
int orig2new[(100 * 1024)];
int ID = 0;
int result[(100 * 1024)];
set<int> activator[(100 * 1024)];
int idfs(int orignode, int origpar = 0) {
  int node = ID++;
  orig2new[orignode] = node;
  new2orig[node] = orignode;
  cnt[node] = 1;
  par[node] = orig2new[origpar];
  adj[node].clear();
  for (const auto &origto : iadj[orignode]) {
    if (origto == origpar) continue;
    cnt[node] += idfs(origto, orignode);
    adj[node].push_back(orig2new[origto]);
  }
  return cnt[node];
}
void dfs(int n) {
  vector<pair<int, int> > cleanup;
  for (const auto &anode : activator[n]) {
    int anode_end = anode + cnt[anode] - 1;
    if (segt_update(segt_active, 0, 0, N, anode, anode, 0) > 0) continue;
    int add = cnt[anode] - segt_update(segt_cnt, 0, 0, N, anode, anode_end, 0);
    segt_update(segt_active, 0, 0, N, anode, anode_end, 1);
    segt_update(segt_cnt, 0, 0, N, anode, anode, add);
    cleanup.push_back(make_pair(anode, add));
  }
  result[n] = segt_update(segt_cnt, 0, 0, N, 0, N, 0);
  for (const auto &to : adj[n]) dfs(to);
  for (const auto &e : cleanup) {
    int anode = e.first, add = e.second;
    int anode_end = anode + cnt[anode] - 1;
    segt_update(segt_active, 0, 0, N, anode, anode_end, -1);
    segt_update(segt_cnt, 0, 0, N, anode, anode, -add);
  }
}
int main() {
  cin >> N >> K;
  for (int i = (0); i < (N - 1); i++) {
    int a, b;
    cin >> a >> b;
    iadj[a].push_back(b);
    iadj[b].push_back(a);
  }
  orig2new[0] = -1;
  idfs(1);
  for (int i = (0); i < (K); i++) {
    int a, b;
    cin >> a >> b;
    a = orig2new[a];
    b = orig2new[b];
    activator[a].insert(a);
    activator[a].insert(b);
    activator[b].insert(a);
    activator[b].insert(b);
  }
  dfs(orig2new[1]);
  for (int i = (1); i < (N + 1); i++) {
    if (i > 1) cout << " ";
    cout << max(0, result[orig2new[i]] - 1);
  }
  cout << endl;
}
