#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
int n, m, num, head[N], que[N];
int root, Siz, size[N], maxson[N], a[N], dis[N], q[N], judge[N];
long long ans;
bool vis[N];
struct edge {
  int next, to;
} e[N << 1];
void add(int from, int to) {
  e[++num].next = head[from], e[num].to = to, head[from] = num;
  e[++num].next = head[to], e[num].to = from, head[to] = num;
}
void getroot(int x, int fa) {
  maxson[x] = 0, size[x] = 1;
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa && !vis[e[i].to]) {
      getroot(e[i].to, x);
      maxson[x] = std::max(maxson[x], size[e[i].to]);
      size[x] += size[e[i].to];
    }
  maxson[x] = std::max(maxson[x], Siz - maxson[x]);
  if (maxson[x] < maxson[root]) root = x;
}
void dfs(int x, int fa) {
  a[++a[0]] = dis[x];
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa && !vis[e[i].to]) {
      dis[e[i].to] = dis[x] + 1;
      dfs(e[i].to, x);
    }
}
void calc(int u) {
  int p = 0;
  for (int i = head[u]; i; i = e[i].next)
    if (!vis[e[i].to]) {
      a[0] = 0, dis[e[i].to] = 1;
      dfs(e[i].to, u);
      for (int j = a[0]; j; --j)
        if (m - a[j] >= 0) ans += judge[m - a[j]];
      for (int j = a[0]; j; --j)
        if (a[j] <= m) ++judge[a[j]], q[++p] = a[j];
    }
  for (int i = 1; i <= p; ++i) judge[q[i]] = 0;
}
void solve(int u) {
  vis[u] = judge[0] = 1;
  calc(u);
  for (int i = head[u]; i; i = e[i].next)
    if (!vis[e[i].to]) {
      Siz = size[e[i].to], maxson[root = 0] = 2147483647;
      getroot(e[i].to, 0);
      solve(root);
    }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v), add(u, v);
  maxson[root] = Siz = n;
  getroot(1, 0);
  solve(root);
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Your challenge is to write a cpp solution to 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 N = 1e5 + 2;
int n, m, num, head[N], que[N];
int root, Siz, size[N], maxson[N], a[N], dis[N], q[N], judge[N];
long long ans;
bool vis[N];
struct edge {
  int next, to;
} e[N << 1];
void add(int from, int to) {
  e[++num].next = head[from], e[num].to = to, head[from] = num;
  e[++num].next = head[to], e[num].to = from, head[to] = num;
}
void getroot(int x, int fa) {
  maxson[x] = 0, size[x] = 1;
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa && !vis[e[i].to]) {
      getroot(e[i].to, x);
      maxson[x] = std::max(maxson[x], size[e[i].to]);
      size[x] += size[e[i].to];
    }
  maxson[x] = std::max(maxson[x], Siz - maxson[x]);
  if (maxson[x] < maxson[root]) root = x;
}
void dfs(int x, int fa) {
  a[++a[0]] = dis[x];
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa && !vis[e[i].to]) {
      dis[e[i].to] = dis[x] + 1;
      dfs(e[i].to, x);
    }
}
void calc(int u) {
  int p = 0;
  for (int i = head[u]; i; i = e[i].next)
    if (!vis[e[i].to]) {
      a[0] = 0, dis[e[i].to] = 1;
      dfs(e[i].to, u);
      for (int j = a[0]; j; --j)
        if (m - a[j] >= 0) ans += judge[m - a[j]];
      for (int j = a[0]; j; --j)
        if (a[j] <= m) ++judge[a[j]], q[++p] = a[j];
    }
  for (int i = 1; i <= p; ++i) judge[q[i]] = 0;
}
void solve(int u) {
  vis[u] = judge[0] = 1;
  calc(u);
  for (int i = head[u]; i; i = e[i].next)
    if (!vis[e[i].to]) {
      Siz = size[e[i].to], maxson[root = 0] = 2147483647;
      getroot(e[i].to, 0);
      solve(root);
    }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v), add(u, v);
  maxson[root] = Siz = n;
  getroot(1, 0);
  solve(root);
  printf("%lld\n", ans);
  return 0;
}

```