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 N = 1e6 + 7;
int n, vis[N], pos1[N], pos2[N];
vector<int> g[N], q[N];
vector<int> ord;
int sz[N], ans[N];
int dfs(int x) {
  sz[x] = true;
  pos1[x] = ((int)ord.size());
  for (auto i : g[x])
    if (!sz[i]) sz[x] += dfs(i);
  ord.push_back(x);
  pos2[x] = ((int)ord.size());
  return sz[x];
}
int cnt[N], val[N];
void calc(int l, int r, int pl, int sum = 0, int tag = 1, int s = 0,
          int e = n) {
  if (s >= r || e <= l) return;
  if (s >= l && e <= r) {
    val[tag] += pl;
    if (val[tag] == 0 && pl == -1) cnt[tag] = cnt[2 * tag] + cnt[2 * tag + 1];
    if (val[tag] == 1 && pl == 1) cnt[tag] = e - s;
    return;
  }
  int mid = (s + e) / 2;
  calc(l, r, pl, sum, tag * 2 + 0, s, mid);
  calc(l, r, pl, sum, tag * 2 + 1, mid, e);
  if (val[tag] == 0) cnt[tag] = cnt[tag * 2] + cnt[tag * 2 + 1];
}
void solve(int x) {
  vis[x] = true;
  for (auto i : q[x]) calc(pos1[i], pos2[i], 1);
  ans[x] = max(0, cnt[1] - 1);
  for (auto i : g[x])
    if (!vis[i]) solve(i);
  for (auto i : q[x]) calc(pos1[i], pos2[i], -1);
}
int32_t main() {
  ios::sync_with_stdio(0);
  int Q;
  cin >> n >> Q;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  while (Q--) {
    int x, y;
    cin >> x >> y;
    q[x].push_back(y);
    q[y].push_back(x);
  }
  dfs(1);
  for (int i = 1; i <= n; i++) {
    if (((int)q[i].size())) q[i].push_back(i);
  }
  solve(1);
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}
