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 MAXN = 1e5 + 10;
map<int, vector<int>> mp;
vector<int> adj[MAXN];
int fn[MAXN], st[MAXN];
int ans[MAXN];
int lz[MAXN * 4];
pair<int, int> seg[MAXN * 4];
int a[MAXN];
int n, m;
pair<int, int> mn(const pair<int, int> &p1, const pair<int, int> &p2) {
  if (p1.first == p2.first) return {p1.first, p1.second + p2.second};
  return min(p1, p2);
}
void build(int b = 0, int e = n, int id = 1) {
  if (e - b == 1) {
    seg[id].second = 1;
    return;
  }
  int mid = (b + e) >> 1;
  build(b, mid, id << 1);
  build(mid, e, id << 1 ^ 1);
  seg[id] = mn(seg[id << 1], seg[id << 1 ^ 1]);
}
void update1(int l, int r, int b = 0, int e = n, int id = 1) {
  if (b >= r || e <= l) return;
  if (l <= b && e <= r) {
    ++lz[id];
    ++seg[id].first;
    return;
  }
  int mid = (b + e) >> 1;
  update1(l, r, b, mid, id << 1);
  update1(l, r, mid, e, id << 1 ^ 1);
  seg[id] = mn(seg[id << 1], seg[id << 1 ^ 1]);
  seg[id].first += lz[id];
}
void update2(int l, int r, int b = 0, int e = n, int id = 1) {
  if (b >= r || e <= l) return;
  if (l <= b && e <= r) {
    --lz[id];
    --seg[id].first;
    return;
  }
  int mid = (b + e) >> 1;
  update2(l, r, b, mid, id << 1);
  update2(l, r, mid, e, id << 1 ^ 1);
  seg[id] = mn(seg[id << 1], seg[id << 1 ^ 1]);
  seg[id].first += lz[id];
}
int get_(int x, int b = 0, int e = n, int id = 1, int o = 0) {
  if (e - b == 1) return seg[id].first + o;
  int mid = (b + e) >> 1;
  if (x < mid) {
    return get_(x, b, mid, id << 1, o + lz[id]);
  } else {
    return get_(x, mid, e, id << 1 ^ 1, o + lz[id]);
  }
}
int DFS_t;
void DFS1(int v = 1, int pre = -1) {
  st[v] = DFS_t++;
  for (int i : adj[v])
    if (pre != i) DFS1(i, v);
  fn[v] = DFS_t;
}
void DFS(int v = 1, int pre = 0) {
  for (int j : mp[v]) update1(st[j], fn[j]), update1(st[v], fn[v]);
  ans[v] = n - (seg[1].first == 0 ? seg[1].second : 0);
  if (get_(st[v]) != 0) --ans[v];
  for (int i : adj[v]) {
    if (pre == i) continue;
    DFS(i, v);
  }
  for (int j : mp[v]) update2(st[j], fn[j]), update2(st[v], fn[v]);
}
int main() {
  cin >> n >> m;
  build();
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    mp[x].push_back(y);
    mp[y].push_back(x);
  }
  DFS1();
  DFS();
  for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
}
