#include <bits/stdc++.h>
using namespace std;
int i = 1, n, k, ij[50001], ji[50001], a, b, v[50001][501], par[50001], j = 0,
    s[50001], is = 0, vk[50001];
vector<vector<int> > tab(50001);
long long wynn = 0;
int main() {
  scanf("%d %d", &n, &k);
  while (i < n) {
    scanf("%d %d", &a, &b);
    tab[a].push_back(b), tab[b].push_back(a);
    ij[a]++, ij[b]++;
    i++;
  }
  s[0] = 1, is = 1;
  for (int z = 0; z <= n; z++) {
    ji[z] = ij[z];
  }
  while (is > 0) {
    a = s[is - 1];
    if (ij[a] > 0 && tab[a][ij[a] - 1] == par[a]) ij[a]--;
    if (ij[a] > 0)
      b = s[is] = tab[a][ij[a] - 1], par[b] = a, ij[a]--, is++;
    else {
      is--;
      if (par[a] != 0) {
        j = 0, v[a][0] = 1;
        while (j < k) {
          v[par[a]][j + 1] += v[a][j];
          j++;
        }
      }
    }
  }
  v[1][0] = 1;
  s[0] = 1, is = 1;
  for (int z = 0; z <= n; z++) {
    ij[z] = ji[z];
  }
  while (is > 0) {
    a = s[is - 1];
    if (ij[a] > 0 && tab[a][ij[a] - 1] == par[a]) ij[a]--;
    if (ij[a] > 0) {
      b = s[is] = tab[a][ij[a] - 1], par[b] = a, ij[a]--, is++;
      j = 0;
      while (j < k) {
        vk[j] = v[b][j];
        j++;
      }
      j = 0;
      while (j < k) {
        if (j > 0) v[b][j + 1] -= vk[j - 1];
        v[b][j + 1] += v[a][j];
        j++;
      }
      wynn += v[b][k];
    } else
      is--;
  }
  wynn += v[1][k];
  printf("%lld", wynn / 2);
  return 0;
}

### Prompt

Please formulate 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;
int i = 1, n, k, ij[50001], ji[50001], a, b, v[50001][501], par[50001], j = 0,
    s[50001], is = 0, vk[50001];
vector<vector<int> > tab(50001);
long long wynn = 0;
int main() {
  scanf("%d %d", &n, &k);
  while (i < n) {
    scanf("%d %d", &a, &b);
    tab[a].push_back(b), tab[b].push_back(a);
    ij[a]++, ij[b]++;
    i++;
  }
  s[0] = 1, is = 1;
  for (int z = 0; z <= n; z++) {
    ji[z] = ij[z];
  }
  while (is > 0) {
    a = s[is - 1];
    if (ij[a] > 0 && tab[a][ij[a] - 1] == par[a]) ij[a]--;
    if (ij[a] > 0)
      b = s[is] = tab[a][ij[a] - 1], par[b] = a, ij[a]--, is++;
    else {
      is--;
      if (par[a] != 0) {
        j = 0, v[a][0] = 1;
        while (j < k) {
          v[par[a]][j + 1] += v[a][j];
          j++;
        }
      }
    }
  }
  v[1][0] = 1;
  s[0] = 1, is = 1;
  for (int z = 0; z <= n; z++) {
    ij[z] = ji[z];
  }
  while (is > 0) {
    a = s[is - 1];
    if (ij[a] > 0 && tab[a][ij[a] - 1] == par[a]) ij[a]--;
    if (ij[a] > 0) {
      b = s[is] = tab[a][ij[a] - 1], par[b] = a, ij[a]--, is++;
      j = 0;
      while (j < k) {
        vk[j] = v[b][j];
        j++;
      }
      j = 0;
      while (j < k) {
        if (j > 0) v[b][j + 1] -= vk[j - 1];
        v[b][j + 1] += v[a][j];
        j++;
      }
      wynn += v[b][k];
    } else
      is--;
  }
  wynn += v[1][k];
  printf("%lld", wynn / 2);
  return 0;
}

```