#include <bits/stdc++.h>
using namespace std;
const int dr[]{-1, -1, 0, 1, 1, 1, 0, -1};
const int dc[]{0, 1, 1, 1, 0, -1, -1, -1};
void run() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
class centroid_decomposition {
  vector<bool> visited;
  vector<int> size;
  void dfsSize(int node) {
    visited[node] = true;
    size[node] = 1;
    for (int ch : adj[node])
      if (!visited[node]) {
        dfsSize(ch);
        size[node] += size[ch];
      }
    visited[node] = false;
  }
  int getCenter(int node, int size_of_tree) {
    visited[node] = true;
    bool is_centroid = (2 * size_of_tree - 2 * size[node] <= size_of_tree);
    for (int ch : adj[node])
      if (!visited[ch])
        if (2 * size[ch] > size_of_tree) is_centroid = false;
    if (is_centroid) return node;
    for (int ch : adj[node])
      if (!visited[ch]) {
        int cur = getCenter(ch, size_of_tree);
        if (~cur) {
          visited[node] = false;
          return cur;
        }
      }
    visited[node] = false;
    return -1;
  }
  int getCentroid(int src) {
    dfsSize(src);
    int centroid = getCenter(src, size[src]);
    assert(centroid != -1);
    solve(centroid);
    return centroid;
  }
  int decomposeTree(int root) {
    root = getCentroid(root);
    for (int ch : adj[root])
      if (!visited[ch]) {
        decomposeTree(ch);
      }
    return root;
  }
  vector<int> cnt;
  void addSubtree(int node, int dist) {
    if (dist > k) return;
    visited[node] = true;
    cnt[dist]++;
    for (int ch : adj[node])
      if (!visited[ch]) addSubtree(ch, dist + 1);
    visited[node] = false;
  }
  void calc(int node, int dist) {
    if (dist > k) return;
    visited[node] = true;
    ans += cnt[k - dist];
    for (int ch : adj[node])
      if (!visited[ch]) calc(ch, dist + 1);
    visited[node] = false;
  }
  void solve(int root) {
    visited[root] = true;
    cnt = vector<int>(k + 1);
    cnt[0]++;
    for (int ch : adj[root])
      if (!visited[ch]) {
        calc(ch, 1);
        addSubtree(ch, 1);
      }
  }

 public:
  vector<vector<int>> adj, centroidTree;
  long long ans = 0;
  int n, root, k;
  centroid_decomposition(vector<vector<int>> &adj, int k) : adj(adj), k(k) {
    n = (int)adj.size() - 1;
    size = vector<int>(n + 1);
    centroidTree = vector<vector<int>>(n + 1);
    visited = vector<bool>(n + 1);
    root = decomposeTree(1);
  }
};
int main() {
  run();
  int n, k;
  cin >> n >> k;
  vector<vector<int>> adj(n + 1);
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  cout << centroid_decomposition(adj, k).ans << "\n";
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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 dr[]{-1, -1, 0, 1, 1, 1, 0, -1};
const int dc[]{0, 1, 1, 1, 0, -1, -1, -1};
void run() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
class centroid_decomposition {
  vector<bool> visited;
  vector<int> size;
  void dfsSize(int node) {
    visited[node] = true;
    size[node] = 1;
    for (int ch : adj[node])
      if (!visited[node]) {
        dfsSize(ch);
        size[node] += size[ch];
      }
    visited[node] = false;
  }
  int getCenter(int node, int size_of_tree) {
    visited[node] = true;
    bool is_centroid = (2 * size_of_tree - 2 * size[node] <= size_of_tree);
    for (int ch : adj[node])
      if (!visited[ch])
        if (2 * size[ch] > size_of_tree) is_centroid = false;
    if (is_centroid) return node;
    for (int ch : adj[node])
      if (!visited[ch]) {
        int cur = getCenter(ch, size_of_tree);
        if (~cur) {
          visited[node] = false;
          return cur;
        }
      }
    visited[node] = false;
    return -1;
  }
  int getCentroid(int src) {
    dfsSize(src);
    int centroid = getCenter(src, size[src]);
    assert(centroid != -1);
    solve(centroid);
    return centroid;
  }
  int decomposeTree(int root) {
    root = getCentroid(root);
    for (int ch : adj[root])
      if (!visited[ch]) {
        decomposeTree(ch);
      }
    return root;
  }
  vector<int> cnt;
  void addSubtree(int node, int dist) {
    if (dist > k) return;
    visited[node] = true;
    cnt[dist]++;
    for (int ch : adj[node])
      if (!visited[ch]) addSubtree(ch, dist + 1);
    visited[node] = false;
  }
  void calc(int node, int dist) {
    if (dist > k) return;
    visited[node] = true;
    ans += cnt[k - dist];
    for (int ch : adj[node])
      if (!visited[ch]) calc(ch, dist + 1);
    visited[node] = false;
  }
  void solve(int root) {
    visited[root] = true;
    cnt = vector<int>(k + 1);
    cnt[0]++;
    for (int ch : adj[root])
      if (!visited[ch]) {
        calc(ch, 1);
        addSubtree(ch, 1);
      }
  }

 public:
  vector<vector<int>> adj, centroidTree;
  long long ans = 0;
  int n, root, k;
  centroid_decomposition(vector<vector<int>> &adj, int k) : adj(adj), k(k) {
    n = (int)adj.size() - 1;
    size = vector<int>(n + 1);
    centroidTree = vector<vector<int>>(n + 1);
    visited = vector<bool>(n + 1);
    root = decomposeTree(1);
  }
};
int main() {
  run();
  int n, k;
  cin >> n >> k;
  vector<vector<int>> adj(n + 1);
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  cout << centroid_decomposition(adj, k).ans << "\n";
}

```