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 = 1e6 + 15;
int n, m, q, x, y, st[MAXN], en[MAXN], lz[MAXN], ans[MAXN];
vector<int> adj[MAXN], arr;
vector<pair<int, int> > lis[MAXN];
pair<int, int> sg[4 * MAXN];
inline void upd(int pos, int b, int e, long long val) {
  lz[pos] += val;
  sg[pos].first += val;
}
inline void shift(int pos, int b, int e) {
  int left = pos << 1, right = left | 1, mid = b + e >> 1;
  upd(left, b, mid, lz[pos]);
  upd(right, mid, e, lz[pos]);
  lz[pos] = 0;
}
void add(int pos, int b, int e, int u, int v, long long val) {
  int l = pos << 1, r = l | 1, mid = b + e >> 1;
  if (v <= b || e <= u) return;
  if (u <= b && e <= v) {
    upd(pos, b, e, val);
    return;
  }
  shift(pos, b, e);
  add(l, b, mid, u, v, val);
  add(r, mid, e, u, v, val);
  sg[pos].first = min(sg[l].first, sg[r].first);
  if (sg[l].first == sg[r].first)
    sg[pos].second = sg[l].second + sg[r].second;
  else if (sg[l].first < sg[r].first)
    sg[pos].second = sg[l].second;
  else
    sg[pos].second = sg[r].second;
}
void dfs(int vert, int par) {
  st[vert] = arr.size();
  arr.push_back(vert);
  for (int i = 0; i < adj[vert].size(); i++)
    if (adj[vert][i] != par) dfs(adj[vert][i], vert);
  en[vert] = arr.size();
}
void bld(int pos, int s, int e) {
  int left = pos << 1, right = left | 1, mid = s + e >> 1;
  if (s == e - 1) {
    sg[pos] = {0, 1};
    return;
  }
  bld(left, s, mid);
  bld(right, mid, e);
  sg[pos] = {0, e - s};
}
void dfs_ans(int vert, int par) {
  for (int i = 0; i < lis[vert].size(); i++) {
    add(1, 0, n, st[vert], en[vert], 1);
    add(1, 0, n, st[lis[vert][i].first], en[lis[vert][i].first], 1);
  }
  ans[vert] = max(0, n - 1 - (!(sg[1].first)) * sg[1].second);
  for (int i = 0; i < adj[vert].size(); i++)
    if (adj[vert][i] != par) dfs_ans(adj[vert][i], vert);
  for (int i = 0; i < lis[vert].size(); i++) {
    add(1, 0, n, st[vert], en[vert], -1);
    add(1, 0, n, st[lis[vert][i].first], en[lis[vert][i].first], -1);
  }
}
inline void input() {
  cin >> n >> q;
  for (int i = 0; i < n - 1; i++) {
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  while (q--) {
    cin >> x >> y;
    lis[x].push_back({y, q});
    lis[y].push_back({x, q});
  }
}
inline void output() {
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
  cout << '\n';
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  input();
  dfs(1, 0);
  bld(1, 0, n);
  dfs_ans(1, 0);
  output();
}
