#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 50;
int to[MAXN << 1], nxt[MAXN << 1], head[MAXN], ds[MAXN << 1], cnt;
inline void add_edge(int u, int fa, int a) {
  to[++cnt] = fa;
  nxt[cnt] = head[u];
  head[u] = cnt;
  ds[cnt] = a;
  to[++cnt] = u;
  nxt[cnt] = head[fa];
  head[fa] = cnt;
  ds[cnt] = a;
}
int n, k, x, y;
int f[MAXN], dep[MAXN], siz[MAXN], vis[MAXN], que[MAXN];
int top, root, sum;
long long ans;
void getroot(int u, int fa) {
  siz[u] = 1;
  f[u] = 0;
  for (int i = head[u]; i; i = nxt[i])
    if (to[i] != fa && !vis[to[i]]) {
      getroot(to[i], u);
      siz[u] += siz[to[i]];
      f[u] = f[u] > siz[to[i]] ? f[u] : siz[to[i]];
    }
  f[u] = f[u] > sum - siz[u] ? f[u] : sum - siz[u];
  if (f[u] < f[root]) root = u;
}
void dp(int u, int fa) {
  que[++top] = dep[u];
  for (int i = head[u]; i; i = nxt[i])
    if (to[i] != fa && !vis[to[i]]) {
      dep[to[i]] = dep[u] + ds[i];
      dp(to[i], u);
    }
}
int buf[50010];
int calc(int u, int dis) {
  dep[u] = dis;
  top = 0;
  dp(u, 0);
  int res = 0, R = top;
  sort(que + 1, que + top + 1);
  for (register int i = 1; i <= top; ++i)
    while (que[R] > k) R--;
  int l = 1;
  for (register int r = R; r; r--) {
    while (que[l] + que[r] < k && l < r) l++;
    int tmp = 0, L = l;
    while (que[L] + que[r] == k && L < r) L++, tmp++;
    res += tmp;
    if (l >= r) break;
  }
  return res;
}
void solve(int u) {
  ans += calc(u, 0);
  vis[u] = 1;
  for (int i = head[u]; i; i = nxt[i])
    if (!vis[to[i]]) {
      ans -= calc(to[i], ds[i]);
      root = 0;
      sum = siz[to[i]];
      getroot(to[i], 0);
      solve(root);
    }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &x, &y);
    add_edge(x, y, 1);
  }
  f[0] = sum = n;
  getroot(1, 0);
  solve(root);
  printf("%I64d\n", ans);
}

### Prompt

Create a solution in Cpp for the following problem:

A tree is a connected graph that doesn't contain any cycles.

The distance between two vertices of a tree is the length (in edges) of the shortest path between these vertices.

You are given a tree with n vertices and a positive number k. Find the number of distinct pairs of the vertices which have a distance of exactly k between them. Note that pairs (v, u) and (u, v) are considered to be the same pair.

Input

The first line contains two integers n and k (1 ≤ n ≤ 50000, 1 ≤ k ≤ 500) — the number of vertices and the required distance between the vertices.

Next n - 1 lines describe the edges as "ai bi" (without the quotes) (1 ≤ ai, bi ≤ n, ai ≠ bi), where ai and bi are the vertices connected by the i-th edge. All given edges are different.

Output

Print a single integer — the number of distinct pairs of the tree's vertices which have a distance of exactly k between them.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

5 2
1 2
2 3
3 4
2 5


Output

4


Input

5 3
1 2
2 3
3 4
4 5


Output

2

Note

In the first sample the pairs of vertexes at distance 2 from each other are (1, 3), (1, 5), (3, 5) and (2, 4).

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 50;
int to[MAXN << 1], nxt[MAXN << 1], head[MAXN], ds[MAXN << 1], cnt;
inline void add_edge(int u, int fa, int a) {
  to[++cnt] = fa;
  nxt[cnt] = head[u];
  head[u] = cnt;
  ds[cnt] = a;
  to[++cnt] = u;
  nxt[cnt] = head[fa];
  head[fa] = cnt;
  ds[cnt] = a;
}
int n, k, x, y;
int f[MAXN], dep[MAXN], siz[MAXN], vis[MAXN], que[MAXN];
int top, root, sum;
long long ans;
void getroot(int u, int fa) {
  siz[u] = 1;
  f[u] = 0;
  for (int i = head[u]; i; i = nxt[i])
    if (to[i] != fa && !vis[to[i]]) {
      getroot(to[i], u);
      siz[u] += siz[to[i]];
      f[u] = f[u] > siz[to[i]] ? f[u] : siz[to[i]];
    }
  f[u] = f[u] > sum - siz[u] ? f[u] : sum - siz[u];
  if (f[u] < f[root]) root = u;
}
void dp(int u, int fa) {
  que[++top] = dep[u];
  for (int i = head[u]; i; i = nxt[i])
    if (to[i] != fa && !vis[to[i]]) {
      dep[to[i]] = dep[u] + ds[i];
      dp(to[i], u);
    }
}
int buf[50010];
int calc(int u, int dis) {
  dep[u] = dis;
  top = 0;
  dp(u, 0);
  int res = 0, R = top;
  sort(que + 1, que + top + 1);
  for (register int i = 1; i <= top; ++i)
    while (que[R] > k) R--;
  int l = 1;
  for (register int r = R; r; r--) {
    while (que[l] + que[r] < k && l < r) l++;
    int tmp = 0, L = l;
    while (que[L] + que[r] == k && L < r) L++, tmp++;
    res += tmp;
    if (l >= r) break;
  }
  return res;
}
void solve(int u) {
  ans += calc(u, 0);
  vis[u] = 1;
  for (int i = head[u]; i; i = nxt[i])
    if (!vis[to[i]]) {
      ans -= calc(to[i], ds[i]);
      root = 0;
      sum = siz[to[i]];
      getroot(to[i], 0);
      solve(root);
    }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &x, &y);
    add_edge(x, y, 1);
  }
  f[0] = sum = n;
  getroot(1, 0);
  solve(root);
  printf("%I64d\n", ans);
}

```