#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 201 * 1001, MOD = 1e9 + 7;
vector<long long> adj[MAXN], query[MAXN];
long long seg[4 * MAXN] = {}, mn[4 * MAXN] = {}, lazy[4 * MAXN] = {},
                  ans[MAXN] = {};
long long st[MAXN] = {}, en[MAXN] = {}, tme = 0;
void dfs_time(long long u, long long p) {
  st[u] = tme++;
  for (auto v : adj[u])
    if (v != p) dfs_time(v, u);
  en[u] = tme;
}
void shift(long long ind) {
  lazy[2 * ind] += lazy[ind];
  mn[2 * ind] += lazy[ind];
  lazy[2 * ind + 1] += lazy[ind];
  mn[2 * ind + 1] += lazy[ind];
  lazy[ind] = 0;
}
void build(long long s, long long e, long long ind) {
  seg[ind] = e - s;
  if (e - s < 2) return;
  long long mid = (e + s) / 2;
  build(s, mid, 2 * ind);
  build(mid, e, 2 * ind + 1);
}
void update(long long l, long long r, long long val, long long s, long long e,
            long long ind) {
  if (l <= s && e <= r) {
    lazy[ind] += val;
    mn[ind] += val;
    return;
  }
  if (e <= l || r <= s) return;
  shift(ind);
  long long mid = (s + e) / 2;
  update(l, r, val, s, mid, 2 * ind);
  update(l, r, val, mid, e, 2 * ind + 1);
  mn[ind] = min(mn[2 * ind], mn[2 * ind + 1]);
  seg[ind] = (mn[2 * ind] == mn[ind] ? seg[2 * ind] : 0) +
             (mn[2 * ind + 1] == mn[ind] ? seg[2 * ind + 1] : 0);
}
long long n;
void dfs(long long u, long long p) {
  if (query[u].size()) update(st[u], en[u], 1, 0, n, 1);
  for (auto v : query[u]) {
    update(st[v], en[v], 1, 0, n, 1);
  }
  ans[u] = (mn[1] == 0 ? n - seg[1] - 1 : n - 1);
  for (auto v : adj[u])
    if (v != p) dfs(v, u);
  if (query[u].size()) update(st[u], en[u], -1, 0, n, 1);
  for (auto v : query[u]) {
    update(st[v], en[v], -1, 0, n, 1);
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long m, x, y;
  cin >> n >> m;
  for (long long i = 1; i < n; i++) {
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  for (long long i = 0; i < m; i++) {
    cin >> x >> y;
    query[x].push_back(y);
    query[y].push_back(x);
  }
  dfs_time(1, 0);
  build(0, n, 1);
  dfs(1, 0);
  for (long long i = 1; i <= n; i++) cout << max(ans[i], 0ll) << ' ';
}

### Prompt

Generate a CPP solution to 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;
const long long MAXN = 201 * 1001, MOD = 1e9 + 7;
vector<long long> adj[MAXN], query[MAXN];
long long seg[4 * MAXN] = {}, mn[4 * MAXN] = {}, lazy[4 * MAXN] = {},
                  ans[MAXN] = {};
long long st[MAXN] = {}, en[MAXN] = {}, tme = 0;
void dfs_time(long long u, long long p) {
  st[u] = tme++;
  for (auto v : adj[u])
    if (v != p) dfs_time(v, u);
  en[u] = tme;
}
void shift(long long ind) {
  lazy[2 * ind] += lazy[ind];
  mn[2 * ind] += lazy[ind];
  lazy[2 * ind + 1] += lazy[ind];
  mn[2 * ind + 1] += lazy[ind];
  lazy[ind] = 0;
}
void build(long long s, long long e, long long ind) {
  seg[ind] = e - s;
  if (e - s < 2) return;
  long long mid = (e + s) / 2;
  build(s, mid, 2 * ind);
  build(mid, e, 2 * ind + 1);
}
void update(long long l, long long r, long long val, long long s, long long e,
            long long ind) {
  if (l <= s && e <= r) {
    lazy[ind] += val;
    mn[ind] += val;
    return;
  }
  if (e <= l || r <= s) return;
  shift(ind);
  long long mid = (s + e) / 2;
  update(l, r, val, s, mid, 2 * ind);
  update(l, r, val, mid, e, 2 * ind + 1);
  mn[ind] = min(mn[2 * ind], mn[2 * ind + 1]);
  seg[ind] = (mn[2 * ind] == mn[ind] ? seg[2 * ind] : 0) +
             (mn[2 * ind + 1] == mn[ind] ? seg[2 * ind + 1] : 0);
}
long long n;
void dfs(long long u, long long p) {
  if (query[u].size()) update(st[u], en[u], 1, 0, n, 1);
  for (auto v : query[u]) {
    update(st[v], en[v], 1, 0, n, 1);
  }
  ans[u] = (mn[1] == 0 ? n - seg[1] - 1 : n - 1);
  for (auto v : adj[u])
    if (v != p) dfs(v, u);
  if (query[u].size()) update(st[u], en[u], -1, 0, n, 1);
  for (auto v : query[u]) {
    update(st[v], en[v], -1, 0, n, 1);
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long m, x, y;
  cin >> n >> m;
  for (long long i = 1; i < n; i++) {
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  for (long long i = 0; i < m; i++) {
    cin >> x >> y;
    query[x].push_back(y);
    query[y].push_back(x);
  }
  dfs_time(1, 0);
  build(0, n, 1);
  dfs(1, 0);
  for (long long i = 1; i <= n; i++) cout << max(ans[i], 0ll) << ' ';
}

```