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.
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 "*a*<sub class="lower-index">*i*</sub> *b*<sub class="lower-index">*i*</sub>" (without the quotes) (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ *n*, *a*<sub class="lower-index">*i*</sub> ≠ *b*<sub class="lower-index">*i*</sub>), where *a*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub> are the vertices connected by the *i*-th edge. All given edges are different.
5 2
1 2
2 3
3 4
2 5
4
5 3
1 2
2 3
3 4
4 5
2
10 1
2 1
3 1
4 3
5 4
6 5
7 1
8 6
9 2
10 6
9
10 2
2 1
3 1
4 3
5 4
6 5
7 1
8 6
9 2
10 6
10
10 3
2 1
3 1
4 3
5 4
6 5
7 1
8 6
9 2
10 6
8
50 3
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
21 20
22 21
23 22
24 23
25 24
26 25
27 26
28 27
29 28
30 29
31 30
32 31
33 32
34 33
35 34
36 35
37 36
38 37
39 38
40 39
41 40
42 41
43 42
44 43
45 44
46 45
47 46
48 47
49 48
50 49
47
50 4
2 1
3 1
4 2
5 2
6 3
7 3
8 4
9 4
10 5
11 5
12 6
13 6
14 7
15 7
16 8
17 8
18 9
19 9
20 10
21 10
22 11
23 11
24 12
25 12
26 13
27 13
28 14
29 14
30 15
31 15
32 16
33 16
34 17
35 17
36 18
37 18
38 19
39 19
40 20
41 20
42 21
43 21
44 22
45 22
46 23
47 23
48 24
49 24
50 25
124
50 5
2 1
3 1
4 2
5 2
6 4
7 4
8 6
9 6
10 8
11 8
12 10
13 10
14 12
15 12
16 14
17 14
18 16
19 16
20 18
21 18
22 20
23 20
24 22
25 22
26 24
27 24
28 26
29 26
30 28
31 28
32 30
33 30
34 32
35 32
36 34
37 34
38 36
39 36
40 38
41 38
42 40
43 40
44 42
45 42
46 44
47 44
48 46
49 46
50 48
84
10 20
2 1
3 2
4 1
5 3
6 4
7 1
8 2
9 7
10 2
0
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> graph_type;

struct Graph {
    graph_type adj;
    vi par, size;
    vector<bool> is_centroid;
    
    Graph(int n): adj(n), par(n, -1), size(n), is_centroid(n) {}
    
    void add_edge(int u, int v, bool bidirected_edge = true) {
        adj[u].push_back(v);
        
        if (bidirected_edge) {
            adj[v].push_back(u);
        }
        else {
            par[v] = u;
        }
    }
};

int k;

/**
 * @graph: graph
 * @root: root
 * @num_nodes: number of nodes on the current sub-graph we're dealing with
 * 
 * return: the Centroid of the subgraph we're dealing with
 * complexity: O(N)
 **/
int find_centroid(Graph& graph, int root, int num_nodes) {
    // find heaviest child, O(N) total
    int heaviest_child = -1;
    for (int v : graph.adj[root]) {
        // ignore nodes that is already a centroid
        if (!graph.is_centroid[v] && v != graph.par[root] && (heaviest_child == -1 || graph.size[v] > graph.size[heaviest_child])) {
            heaviest_child = v;
        }
    }
    
    // met centroid's condition
    if (heaviest_child == -1 || max(graph.size[heaviest_child], num_nodes - graph.size[root]) <= num_nodes / 2) {
        return root;
    }

    // if root is not the centroid, the real centroid must be somewhere in the subtree rooted at the heaviest_child
    return find_centroid(graph, heaviest_child, num_nodes);
}

/**
 * @graph: graph
 * @root: root
 * @decomposed_graph: decomposed graph
 *
 * return: the centroid as the root of this subgraph
 * complexity: O(NlogN) in total
 **/
int decompose_tree(Graph& graph, int root, Graph& decomposed_graph) {
    // find the centroid of current subgraph, O(N)
    int centroid = find_centroid(graph, root, graph.size[root]);
     
    // mark as centroid, O(N)
    graph.is_centroid[centroid] = true;
    for (int p = graph.par[centroid]; p != -1 && !graph.is_centroid[p]; p = graph.par[p]) {
        graph.size[p] -= graph.size[centroid];
    }
    
    // decompose subtree rooted at centroid
    for (int v : graph.adj[centroid]) {
        if (v != graph.par[centroid] && !graph.is_centroid[v]) {
            decomposed_graph.add_edge(centroid, decompose_tree(graph, v, decomposed_graph), false);
        }
    }

    // subgraph rooted at root is still not decomposed completely
    if (centroid != root) {
        decomposed_graph.add_edge(centroid, decompose_tree(graph, root, decomposed_graph), false);
    }
    
    return centroid;
}

/**
 * @graph: graph
 * @root: root
 *
 * return: size of subtree rooted at root
 * complexity: O(N)
 **/
int cal_sizes(Graph& graph, int root) {
    graph.size[root] = 1;
    for (int v : graph.adj[root]) {
        if (v != graph.par[root]) {
            graph.par[v] = root;
            graph.size[root] += cal_sizes(graph, v);
        }
    }

    return graph.size[root];
}

/**
 * @graph: graph
 * @root: root
 * @par: recent node that's been visited
 * @distance: distance from the caller node
 * @count: count[i] = num of nodes that has distance from caller node of i
 *
 * complexity: O(N)
 **/
void cal_nodes(Graph& graph, int root, int par, int distance, unordered_map<int, int>& count) {
    count[distance]++;
    for (int v : graph.adj[root]) {
        if (v != par && distance + 1 <= k && !graph.is_centroid[v]) {
            cal_nodes(graph, v, root, distance + 1, count);
        }
    }
}

/**
 * @graph: graph
 * @decomposed_graph: the centroid tree of graph
 * @root: root
 *
 * return: num of pairs that have distance of k in the decomposed tree rooted at root
 * complexity: O(NlogN)
 **/
int cal_paths(Graph& graph, Graph& decomposed_graph, int root) {
    int res = 0;
    
    // reuse is_centroid as visited
    graph.is_centroid[root] = true;
    
    // the depth may be much less than k so dont need to initialize a vector of k
    unordered_map<int, int> count;
    count[0] = 1; // dist(root, root) = 0

    // count paths that starts and ends in decomposed graph rooted at root, and goes through root
    // O(N) in total
    for (int v : graph.adj[root]) {
        if (!graph.is_centroid[v] && v != decomposed_graph.par[root]) {
            unordered_map<int, int> count_v;
            count_v[0] = 0;
            cal_nodes(graph, v, root, 1, count_v); // distance starts from 1
            
            if (count.size() < count_v.size()) {
                count.swap(count_v);
            }
            
            for (auto it = count.begin(); it != count.end(); ++it) {
                res += it->second * count_v[k - it->first];
            }

            for (auto it = count_v.begin(); it != count_v.end(); ++it) {
                count[it->first] += it->second;
            }
        }
    }

    for (int v : decomposed_graph.adj[root]) {
        if (v != decomposed_graph.par[root]) {
            res += cal_paths(graph, decomposed_graph, v);
        }
    }

    return res;
}

int main() {
    int n;
    cin >> n >> k;
    Graph graph(n);
    for (int i = 1, x, y; i < n; ++i) {
        cin >> x >> y;
        graph.add_edge(x - 1, y - 1);
    }

    // cal par and size first
    cal_sizes(graph, 0);

    // decompose graph
    Graph decomposed_graph(n);
    int centroid = decompose_tree(graph, 0, decomposed_graph);

    graph.is_centroid.assign(n, false); // reuse as visited
    cout << cal_paths(graph, decomposed_graph, centroid);
}
