#include <bits/stdc++.h>
using namespace std;
const int maxn = 50000 + 10;
const int inf = 0x3f3f3f3f;
int n, k, rt, maxp[maxn], siz[maxn], dis[maxn], vis[maxn], rem[maxn],
    judge[maxn], q[maxn], cnt, sum, ans;
int head[maxn], to[maxn << 1], nxt[maxn << 1], tot;
inline int read() {
  register int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  return (f == 1) ? x : -x;
}
inline void add(int x, int y) {
  to[++tot] = y;
  nxt[tot] = head[x];
  head[x] = tot;
}
void getrt(int x, int fa) {
  siz[x] = 1;
  maxp[x] = 0;
  for (int i = head[x], y; i; i = nxt[i]) {
    y = to[i];
    if (y == fa || vis[y]) continue;
    getrt(y, x);
    siz[x] += siz[y];
    maxp[x] = max(maxp[x], siz[y]);
  }
  maxp[x] = max(maxp[x], sum - siz[x]);
  if (maxp[x] < maxp[rt]) rt = x;
}
void getdis(int x, int fa) {
  rem[++cnt] = dis[x];
  ans += judge[k - dis[x]];
  for (int i = head[x], y; i; i = nxt[i]) {
    y = to[i];
    if (y == fa || vis[y]) continue;
    dis[y] = dis[x] + 1;
    getdis(y, x);
  }
}
void calc(int x) {
  int p = 0;
  for (int i = head[x], y; i; i = nxt[i]) {
    y = to[i];
    if (vis[y]) continue;
    cnt = 0;
    judge[0] = dis[y] = 1;
    getdis(y, x);
    for (int j = 1; j <= cnt; j++)
      if (rem[j] <= k) judge[rem[j]]++, q[++p] = rem[j];
  }
  for (int i = 1; i <= p; i++) judge[q[i]] = 0;
}
void solve(int x) {
  vis[x] = 1;
  calc(x);
  for (int i = head[x], y; i; i = nxt[i]) {
    y = to[i];
    if (vis[y]) continue;
    sum = siz[y];
    rt = 0;
    getrt(y, x);
    solve(rt);
  }
}
int main() {
  n = read(), k = read();
  int x, y;
  for (int i = 1; i < n; i++) {
    x = read(), y = read();
    add(x, y);
    add(y, x);
  }
  maxp[0] = inf;
  sum = n;
  getrt(1, 0);
  getdis(1, 0);
  solve(rt);
  printf("%d\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 maxn = 50000 + 10;
const int inf = 0x3f3f3f3f;
int n, k, rt, maxp[maxn], siz[maxn], dis[maxn], vis[maxn], rem[maxn],
    judge[maxn], q[maxn], cnt, sum, ans;
int head[maxn], to[maxn << 1], nxt[maxn << 1], tot;
inline int read() {
  register int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  return (f == 1) ? x : -x;
}
inline void add(int x, int y) {
  to[++tot] = y;
  nxt[tot] = head[x];
  head[x] = tot;
}
void getrt(int x, int fa) {
  siz[x] = 1;
  maxp[x] = 0;
  for (int i = head[x], y; i; i = nxt[i]) {
    y = to[i];
    if (y == fa || vis[y]) continue;
    getrt(y, x);
    siz[x] += siz[y];
    maxp[x] = max(maxp[x], siz[y]);
  }
  maxp[x] = max(maxp[x], sum - siz[x]);
  if (maxp[x] < maxp[rt]) rt = x;
}
void getdis(int x, int fa) {
  rem[++cnt] = dis[x];
  ans += judge[k - dis[x]];
  for (int i = head[x], y; i; i = nxt[i]) {
    y = to[i];
    if (y == fa || vis[y]) continue;
    dis[y] = dis[x] + 1;
    getdis(y, x);
  }
}
void calc(int x) {
  int p = 0;
  for (int i = head[x], y; i; i = nxt[i]) {
    y = to[i];
    if (vis[y]) continue;
    cnt = 0;
    judge[0] = dis[y] = 1;
    getdis(y, x);
    for (int j = 1; j <= cnt; j++)
      if (rem[j] <= k) judge[rem[j]]++, q[++p] = rem[j];
  }
  for (int i = 1; i <= p; i++) judge[q[i]] = 0;
}
void solve(int x) {
  vis[x] = 1;
  calc(x);
  for (int i = head[x], y; i; i = nxt[i]) {
    y = to[i];
    if (vis[y]) continue;
    sum = siz[y];
    rt = 0;
    getrt(y, x);
    solve(rt);
  }
}
int main() {
  n = read(), k = read();
  int x, y;
  for (int i = 1; i < n; i++) {
    x = read(), y = read();
    add(x, y);
    add(y, x);
  }
  maxp[0] = inf;
  sum = n;
  getrt(1, 0);
  getdis(1, 0);
  solve(rt);
  printf("%d\n", ans);
  return 0;
}

```