#include <bits/stdc++.h>
using namespace std;
bool check(long long n, long long pos) { return n & (1LL << pos); }
long long Set(long long n, long long pos) { return n = n | (1LL << pos); }
struct segTree {
  long long n;
  vector<long long> tree, lazy, cnt;
  segTree(long long n) : n(n), tree(4 * n, 0), lazy(4 * n, 0), cnt(4 * n, 0) {}
  void init(long long node, long long i, long long j) {
    if (i == j) {
      cnt[node] = 1;
      return;
    }
    init(node * 2, i, (i + j) / 2);
    init(node * 2 + 1, (i + j) / 2 + 1, j);
    cnt[node] = cnt[node * 2] + cnt[node * 2 + 1];
  }
  void propagate(long long node, long long l, long long r) {
    tree[node] += lazy[node];
    if (l != r) lazy[2 * node] += lazy[node], lazy[2 * node + 1] += lazy[node];
    lazy[node] = 0;
  }
  void treeUpdate(long long node, long long l, long long r, long long u,
                  long long v, long long val) {
    long long mid = (l + r) >> 1;
    propagate(node, l, r);
    if (l > v || r < u) return;
    if (l >= u && r <= v) {
      lazy[node] += val;
      propagate(node, l, r);
      return;
    }
    treeUpdate(2 * node, l, mid, u, v, val);
    treeUpdate(2 * node + 1, mid + 1, r, u, v, val);
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
    cnt[node] = 0;
    if (tree[node] == tree[2 * node]) cnt[node] += cnt[node * 2];
    if (tree[node] == tree[2 * node + 1]) cnt[node] += cnt[node * 2 + 1];
  }
  void update(long long l, long long r, long long val) {
    treeUpdate(1, 1, n, l, r, val);
  }
  pair<long long, long long> treeQuery(long long node, long long l, long long r,
                                       long long u, long long v) {
    long long mid = (l + r) >> 1;
    propagate(node, l, r);
    if (l > v || r < u) return {LLONG_MAX, 0};
    if (l >= u && r <= v) return {tree[node], cnt[node]};
    pair<long long, long long> x = treeQuery(2 * node, l, mid, u, v);
    pair<long long, long long> y = treeQuery(2 * node + 1, mid + 1, r, u, v);
    if (x.first == y.first) return {x.first, x.second + y.second};
    return min(x, y);
  }
  pair<long long, long long> query(long long l, long long r) {
    return treeQuery(1, 1, n, l, r);
  }
  long long solve(long long node) {
    pair<long long, long long> ask = query(1, n);
    if (ask.first != 0) return n - 1;
    long long ret = (n - ask.second);
    if (query(node, node).first) ret--;
    return ret;
  }
};
const long long maxn = 100000;
vector<long long> graph[maxn + 5];
vector<long long> qq[maxn + 5];
long long mark;
long long mp[maxn + 5];
segTree tree(maxn);
long long subtree[maxn + 5];
long long ans[maxn + 5];
void dfs(long long node, long long par = 0) {
  ++mark;
  mp[node] = mark;
  subtree[node] = 1;
  for (auto it : graph[node]) {
    if (it == par) continue;
    dfs(it, node);
    subtree[node] += subtree[it];
  }
}
void dfs1(long long node, long long par = 0) {
  for (auto it : qq[node]) {
    long long enode = mp[node];
    long long eit = mp[it];
    tree.update(enode, enode + subtree[node] - 1, 1);
    tree.update(eit, eit + subtree[it] - 1, 1);
  }
  ans[node] = tree.solve(mp[node]);
  for (auto it : graph[node]) {
    if (it == par) continue;
    dfs1(it, node);
  }
  for (auto it : qq[node]) {
    long long enode = mp[node];
    long long eit = mp[it];
    tree.update(enode, enode + subtree[node] - 1, -1);
    tree.update(eit, eit + subtree[it] - 1, -1);
  }
}
int main() {
  long long i, j, k, l, m, n, o, r, q;
  long long testcase;
  long long input, flag, tag;
  scanf("%lld", &n);
  scanf("%lld", &m);
  for (i = 1; i < n; i++) {
    long long u, v;
    scanf("%lld", &u);
    scanf("%lld", &v);
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  mark = 0;
  dfs(1);
  for (i = 1; i <= m; i++) {
    long long u, v;
    scanf("%lld", &u);
    scanf("%lld", &v);
    qq[u].push_back(v);
    qq[v].push_back(u);
  }
  tree.n = n;
  tree.init(1, 1, n);
  dfs1(1);
  for (i = 1; i <= n; i++) {
    printf("%lld ", ans[i]);
  }
  printf("\n");
}

### Prompt

In CPP, your task is to solve the following problem:

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 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
bool check(long long n, long long pos) { return n & (1LL << pos); }
long long Set(long long n, long long pos) { return n = n | (1LL << pos); }
struct segTree {
  long long n;
  vector<long long> tree, lazy, cnt;
  segTree(long long n) : n(n), tree(4 * n, 0), lazy(4 * n, 0), cnt(4 * n, 0) {}
  void init(long long node, long long i, long long j) {
    if (i == j) {
      cnt[node] = 1;
      return;
    }
    init(node * 2, i, (i + j) / 2);
    init(node * 2 + 1, (i + j) / 2 + 1, j);
    cnt[node] = cnt[node * 2] + cnt[node * 2 + 1];
  }
  void propagate(long long node, long long l, long long r) {
    tree[node] += lazy[node];
    if (l != r) lazy[2 * node] += lazy[node], lazy[2 * node + 1] += lazy[node];
    lazy[node] = 0;
  }
  void treeUpdate(long long node, long long l, long long r, long long u,
                  long long v, long long val) {
    long long mid = (l + r) >> 1;
    propagate(node, l, r);
    if (l > v || r < u) return;
    if (l >= u && r <= v) {
      lazy[node] += val;
      propagate(node, l, r);
      return;
    }
    treeUpdate(2 * node, l, mid, u, v, val);
    treeUpdate(2 * node + 1, mid + 1, r, u, v, val);
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
    cnt[node] = 0;
    if (tree[node] == tree[2 * node]) cnt[node] += cnt[node * 2];
    if (tree[node] == tree[2 * node + 1]) cnt[node] += cnt[node * 2 + 1];
  }
  void update(long long l, long long r, long long val) {
    treeUpdate(1, 1, n, l, r, val);
  }
  pair<long long, long long> treeQuery(long long node, long long l, long long r,
                                       long long u, long long v) {
    long long mid = (l + r) >> 1;
    propagate(node, l, r);
    if (l > v || r < u) return {LLONG_MAX, 0};
    if (l >= u && r <= v) return {tree[node], cnt[node]};
    pair<long long, long long> x = treeQuery(2 * node, l, mid, u, v);
    pair<long long, long long> y = treeQuery(2 * node + 1, mid + 1, r, u, v);
    if (x.first == y.first) return {x.first, x.second + y.second};
    return min(x, y);
  }
  pair<long long, long long> query(long long l, long long r) {
    return treeQuery(1, 1, n, l, r);
  }
  long long solve(long long node) {
    pair<long long, long long> ask = query(1, n);
    if (ask.first != 0) return n - 1;
    long long ret = (n - ask.second);
    if (query(node, node).first) ret--;
    return ret;
  }
};
const long long maxn = 100000;
vector<long long> graph[maxn + 5];
vector<long long> qq[maxn + 5];
long long mark;
long long mp[maxn + 5];
segTree tree(maxn);
long long subtree[maxn + 5];
long long ans[maxn + 5];
void dfs(long long node, long long par = 0) {
  ++mark;
  mp[node] = mark;
  subtree[node] = 1;
  for (auto it : graph[node]) {
    if (it == par) continue;
    dfs(it, node);
    subtree[node] += subtree[it];
  }
}
void dfs1(long long node, long long par = 0) {
  for (auto it : qq[node]) {
    long long enode = mp[node];
    long long eit = mp[it];
    tree.update(enode, enode + subtree[node] - 1, 1);
    tree.update(eit, eit + subtree[it] - 1, 1);
  }
  ans[node] = tree.solve(mp[node]);
  for (auto it : graph[node]) {
    if (it == par) continue;
    dfs1(it, node);
  }
  for (auto it : qq[node]) {
    long long enode = mp[node];
    long long eit = mp[it];
    tree.update(enode, enode + subtree[node] - 1, -1);
    tree.update(eit, eit + subtree[it] - 1, -1);
  }
}
int main() {
  long long i, j, k, l, m, n, o, r, q;
  long long testcase;
  long long input, flag, tag;
  scanf("%lld", &n);
  scanf("%lld", &m);
  for (i = 1; i < n; i++) {
    long long u, v;
    scanf("%lld", &u);
    scanf("%lld", &v);
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  mark = 0;
  dfs(1);
  for (i = 1; i <= m; i++) {
    long long u, v;
    scanf("%lld", &u);
    scanf("%lld", &v);
    qq[u].push_back(v);
    qq[v].push_back(u);
  }
  tree.n = n;
  tree.init(1, 1, n);
  dfs1(1);
  for (i = 1; i <= n; i++) {
    printf("%lld ", ans[i]);
  }
  printf("\n");
}

```