/////////////////////////////////////////////////////////////////////////////////////////////
// SUMMARY:                                                                                //
/////////////////////////////////////////////////////////////////////////////////////////////
//     Approach (1A):    DFS Recursive seems to work BEST on HackerRank test-cases.        //
//                       All Hacker-Rank Test-Cases pass OK. No wrong answers. No TLEs.    //
//                                                                                         //
//     Approach (1B):    DFS Iterative fails ONE test-case (TLE). Everything else passes.  //
//                          Specifically, only TC-21 fails due to TLE.                     //
//                          But I verified that Code Answer matches Expected Answer        //
//                          So it gives correct answer, but takes too much time.           //
//                                                                                         //
//     Approach (2):     BFS Iterative fails ONE test-case (TLE). Everything else passes.  //
//                          Specifically, only TC-21 fails due to TLE.                     //
//                          But I verified that Code Answer matches Expected Answer        //
//                          So it gives correct answer, but takes too much time.           //
/////////////////////////////////////////////////////////////////////////////////////////////


class Result {

    // Verbose Debug Print Toggle Switches
    private static final boolean vDbgL1 = false;
    private static final boolean vDbgL2 = false;
    private static final boolean vDbgL3 = false;
    private static final boolean vDbgL4 = false;
    private static final boolean vDbgL5 = false;

    // Verbose Debug Print - Controls for LARGE Structures with LARGE num of elements
    private static final int VDBG_MAX_SUBTREE_NODE_SIZE = 50;
    private static final int VDBG_MAX_SUBTREE_ADJ_GRAPH_SIZE = 50;
    private static final int VDBG_MAX_ADJ_GRAPH_SIZE = 50;
    private static final int VDBG_MAX_DISTINCT_SUB_TREE_ADJ_SET_SIZE = 100;
    private static final int VDBG_MAX_CANON_LEN = 50;


    // Settings for Canonical Hash (String)
    private static final String SINGLE_NODE_SUBTREE_DEFAULT_CAN_HASH_STR = "()";


    // Common Helper Class - representing Adjacency Graph
    private static class AdjGraph {
        private Map<Integer, List<Integer>> adjNodeEdgeLstMap;

        public AdjGraph() {
            this.adjNodeEdgeLstMap = new LinkedHashMap<>();
        }

        public AdjGraph(int numNodes, List<List<Integer>> edges) {
            AdjGraph.verifyNumNodesFromEdges(numNodes, edges);

            this.adjNodeEdgeLstMap =  new LinkedHashMap<>();

            for (List<Integer> edge : edges) {
                int u = edge.get(0), v = edge.get(1);
                this.addEdge(u, v);
            }
        
            if (vDbgL1) {
                String msg = "Built ADJ has >" + this.adjNodeEdgeLstMap.size() + "< elements. ";
                if (this.adjNodeEdgeLstMap.size() <= VDBG_MAX_ADJ_GRAPH_SIZE) {
                    msg += "Built ADJ = >" + this.adjNodeEdgeLstMap + "<";
                }
                System.err.println(msg);
            }
            if (vDbgL2) {
                if (this.adjNodeEdgeLstMap.size() <= VDBG_MAX_ADJ_GRAPH_SIZE) {
                    for (int i = 0; i < this.adjNodeEdgeLstMap.size(); i++) {
                        System.err.println("adj(" + i + "): >" + this.adjNodeEdgeLstMap.get(i) + "<");
                    }
                }
            }
        }

        void addEdge(int u, int v) {
            if (!this.adjNodeEdgeLstMap.containsKey(u)) {
                this.adjNodeEdgeLstMap.put(u, new ArrayList<>());
            }
            this.adjNodeEdgeLstMap.get(u).add(v);

            if (!this.adjNodeEdgeLstMap.containsKey(v)) {
                this.adjNodeEdgeLstMap.put(v, new ArrayList<>());
            }
            this.adjNodeEdgeLstMap.get(v).add(u);
        }
        
        Map<Integer, List<Integer>> getAdj() {
            return this.adjNodeEdgeLstMap;
        }

        private static void verifyNumNodesFromEdges(int numNodes, List<List<Integer>> edges) {

            int maxNodeId = Integer.MIN_VALUE;
            for (List<Integer> edge : edges) {
                maxNodeId = Math.max(maxNodeId, Math.max(edge.get(0), edge.get(1)));
            }

            if (maxNodeId != numNodes) {
                String msg = "UNEXPECTED! maxNodeId=" + maxNodeId + 
                             " != numNodes=" + numNodes + "! Invalid input!";
                System.err.println(msg);
                throw new RuntimeException(msg);
            }

            if (edges.size() != (numNodes - 1)) {
                String msg = "UNEXPECTED! edges.size()=" + edges.size() + 
                         " != (numNodes - 1)=" + (numNodes - 1) + "! Invalid input!";
                System.err.println(msg);
                throw new RuntimeException(msg);
            }

        }

        @Override
        public String toString() {
            return "( A: (" + this.adjNodeEdgeLstMap + ") )";
        }

    }


    // Common Helper Class for DFS Iterative (via Stack) & BFS Iterative (via Queue)
    private static class RelativeNodeDepth {
        int srcNodeId;
        int curNodeId;
        int depthDist;
        
        RelativeNodeDepth(int srcNodeId, int curNodeId, int depthDist) {
            this.srcNodeId = srcNodeId;
            this.curNodeId = curNodeId;
            this.depthDist = depthDist;
        }
        
        public String toString() {
            // return "(R: " + this.srcNodeId + " , C: " + this.curNodeId + 
            //        " , D: " + this.depthDist + ")";
            return "(C: " + this.curNodeId + 
                   " , D: " + this.depthDist + ")";
        }

    }


    // Common Helper Enum - to switch between Algorithms
    private static enum AlgoChoice {
        DFS_Recursive("DFS Recursive"),
        DFS_Iterative("DFS Iterative"),
        BFS_Iterative("BFS Iterative");

        private final String displayName;

        // Constructor
        AlgoChoice(String displayName) {
            this.displayName = displayName;
        }

        // Override toString to return your custom string
        @Override
        public String toString() {
            return this.displayName;
        }
    }


    // Common Helper Function - To construct the Sub-Tree Adjacency Graph
    // Given the "Source / Original Adjacency Graph" + "Set of SubTree Nodes"
    private static AdjGraph constructSubTreeAdj(String algoName, int startNodeId, 
            AdjGraph srcAdjGraph, Set<Integer> curSubTreeNodes) {
        
        AdjGraph curSubTreeAdjGraph = new AdjGraph();

        // Build induced adjacency for subtree
        for (int node : curSubTreeNodes) {
            curSubTreeAdjGraph.adjNodeEdgeLstMap.put(node, new ArrayList<>());
        }

        for (int node : curSubTreeNodes) {
            for (int nei : srcAdjGraph.adjNodeEdgeLstMap.get(node)) {
                if (curSubTreeNodes.contains(nei)) {
                    curSubTreeAdjGraph.adjNodeEdgeLstMap.get(node).add(nei);
                }
            }
        }

        if(vDbgL5) {
            String msg = "For " + algoName + " from Node " + startNodeId + " : ";
            msg += "curSubTreeNodes.size = >" + curSubTreeNodes.size() + "< | ";
            if (curSubTreeNodes.size() <= VDBG_MAX_SUBTREE_NODE_SIZE) {
                msg += "curSubTreeNodes = >" + curSubTreeNodes + "< | ";
            }
            msg += "Constructed : curSubTreeAdjGraph.size = >" +
                    curSubTreeAdjGraph.adjNodeEdgeLstMap.size() + "< | ";
            if (curSubTreeAdjGraph.adjNodeEdgeLstMap.size() <= VDBG_MAX_SUBTREE_ADJ_GRAPH_SIZE) {
                msg += "Constructed : curSubTreeAdjGraph = >" + curSubTreeAdjGraph + "<";
            }
            System.err.println(msg);
        }

        return curSubTreeAdjGraph;

    }


    // Common Helper Function - to find the Center of a Graph
    private static List<Integer> findCenters(AdjGraph subTreeAdjGraph) {
        int size = subTreeAdjGraph.adjNodeEdgeLstMap.size();
        Map<Integer, Integer> degree = new HashMap<Integer, Integer>();
        Queue<Integer> leaves = new LinkedList<Integer>();

        for (int node : subTreeAdjGraph.adjNodeEdgeLstMap.keySet()) {
            int d = subTreeAdjGraph.adjNodeEdgeLstMap.get(node).size();
            degree.put(node, d);
            if (d <= 1) leaves.add(node);
        }

        int remaining = size;
        while (remaining > 2) {
            int leafCount = leaves.size();
            remaining -= leafCount;
            for (int i = 0; i < leafCount; i++) {
                int leaf = leaves.poll();
                for (int nei : subTreeAdjGraph.adjNodeEdgeLstMap.get(leaf)) {
                    degree.put(nei, degree.get(nei) - 1);
                    if (degree.get(nei) == 1) {
                        leaves.add(nei);
                    }
                }
            }
        }

        return new ArrayList<>(leaves);
    }


    // Common Helper Function - to construct the Normalized Minimum Canonical Form
    // which is a Normalized Hashed String Representation of the SubTree Graph
    // As taken from its CENTER. And if multiple centers, then lexicographically minimal.
    private static String findNormMinForm(String algoName, int startNodeId,
                                          AdjGraph curSubTreeAdjGraph) {

        // Find center(s) of this subtree
        List<Integer> centers = findCenters(curSubTreeAdjGraph);

        // Compute canonical forms for each center and pick smallest
        String normMinForm = null;
        List<String> centerCanonForms = new ArrayList<String>();

        // Compute minimal hash among all centers
        for (int c : centers) {
            String curCanonform = canonicalFormStr(c, 0, curSubTreeAdjGraph);
            if (normMinForm == null || curCanonform.compareTo(normMinForm) < 0) {
                normMinForm = curCanonform;
            }
        }            

        if (centers.size() > 2 || centerCanonForms.size() > 2) {
            String errMsg = "UNEXPECTED! centers.size() = >" + centers.size() + "< | " + 
                            "centerCanonForms.size() = >" + centerCanonForms.size() + "<";
            System.err.println(errMsg);
            throw new RuntimeException(errMsg);
        }

        if (vDbgL5) {
            String msg = "For " + algoName + " from Node " + startNodeId + " :: " +  
                        "Subtree has >" + centers.size() + "< center(s) = >" + centers + 
                        "< " + "resulting in >" + centerCanonForms.size() + "< canonical forms";
            msg += ( normMinForm.length() <= VDBG_MAX_CANON_LEN
                     ? "< | And normMinForm = >" + normMinForm + "<"
                     : "< | And normMinForm has >" + normMinForm.length() + "< chars." );
            System.err.println(msg);
        }

        return normMinForm;

    }


    // Common Helper Function - to construct the Canonical Form (Hashed String Representation)
    // Given the Current SubTree's Adj Graph, and the node / parent IDs.
    private static String canonicalFormStr(int node, int parent, AdjGraph curSubTreeAdjGraph) {
        List<String> childrenForms = new ArrayList<>();
        for (int nei : curSubTreeAdjGraph.adjNodeEdgeLstMap.get(node)) {
            if (nei != parent) {
                childrenForms.add(canonicalFormStr(nei, node, curSubTreeAdjGraph));
            }
        }
        Collections.sort(childrenForms);
        return "(" + String.join("", childrenForms) + ")";
    }


    // Common Helper Function - to Print Lengthy Debug Message
    private static void debugPrintFinalDistinctSubTreeAdjSet(
                String algoName, Set<String> distinctSubTreeAdjSet) {

        String msg = algoName + " :: Final: distinctSubTreeAdjSet.size() = >" +
                distinctSubTreeAdjSet.size() + "<";

        if (distinctSubTreeAdjSet.size() <= VDBG_MAX_DISTINCT_SUB_TREE_ADJ_SET_SIZE) {
            msg += "distinctSubTreeAdjSet = >[";
            int setIdx = 0;
            for (String curCanonForm : distinctSubTreeAdjSet) {
                msg += ( curCanonForm.length() <= VDBG_MAX_CANON_LEN
                        ? curCanonForm
                        : "<" + curCanonForm.length() + "_CHARS>");
                if (setIdx != (distinctSubTreeAdjSet.size() - 1)) {
                    msg += ", ";
                }
                setIdx++;
            }
            msg += "]<";
        }

        System.err.println(msg);

    }


    // Depth-First-Search (DFS) - Wrapper around Recursive Method
    private static Set<Integer> dfsRecWrapper(
            int startNodeId, AdjGraph adjGraph, int maxNodeId, int dfsRadius, int remainingDepth) {

        boolean[] visited = new boolean[maxNodeId + 1];

        Set<Integer> curSubTreeNodeSet = new HashSet<Integer>();
        curSubTreeNodeSet.add(startNodeId);

        int numDfsRecNodes = dfsRecursive(startNodeId, adjGraph, curSubTreeNodeSet,
                                          visited, dfsRadius, remainingDepth);

        if (vDbgL1) {
            String msg = "DFS Recursive from Node >" + startNodeId + "< results in " +
                         "numDfsRecNodes = >" + numDfsRecNodes + "< | " +
                         "curSubTreeNodeSet.size() = >" + curSubTreeNodeSet.size() + "< | ";
            if (curSubTreeNodeSet.size() <= VDBG_MAX_SUBTREE_NODE_SIZE) {
                msg += "curSubTreeNodeSet = >" + curSubTreeNodeSet + "<";
            }
            System.err.println(msg);
        }

        return curSubTreeNodeSet;

    }


    // Depth-First-Search (DFS) - Actual Recursive Method
    private static int dfsRecursive(
            int node, AdjGraph adjGraph, Set<Integer> curSubTreeNodeSet, 
            boolean[] visited, int dfsRadius, int remainingDepth) {

        if (vDbgL2) {
            System.err.println("DFS Recursive from Node >" + node + 
                               "< | remainingDepth = >" + remainingDepth + "<");
        }

        visited[node] = true;
        curSubTreeNodeSet.add(node);

        // Base Condition: Terminate Recursive DFS once we have explored upto radius 'r'
        if (remainingDepth == 0) {

            if (vDbgL4) {
                System.err.println("DFS Recursive from Node >" + node + "< " + 
                                   "is at dfsRadius = >" + dfsRadius + "< | Avoiding further DFS!");
            }

            return 1;
        }

        int numDfsRecNodes = 1;

        for (int nei : adjGraph.getAdj().get(node)) {
            if (!visited[nei]) {
                numDfsRecNodes += dfsRecursive(nei, adjGraph, curSubTreeNodeSet, 
                                               visited, dfsRadius, remainingDepth - 1);
            }
        }

        return numDfsRecNodes;

    }


    // Depth-First-Search (DFS) - Non-Recursive / Iterative (via Explicit Stack)
    private static Set<Integer> dfsNonRecIter(
            int startNodeId, AdjGraph adjGraph, int maxNodeId, int dfsRadius) {

        boolean[] visited = new boolean[maxNodeId + 1];
        visited[startNodeId] = true;

        Stack<RelativeNodeDepth> dfsStack = new Stack<RelativeNodeDepth>();
        dfsStack.push(new RelativeNodeDepth(startNodeId, startNodeId, 0));

        int numDfsIterNodes = 0;
        
        Set<Integer> curSubTreeNodeSet = new HashSet<Integer>();
        curSubTreeNodeSet.add(startNodeId);

        while (!dfsStack.isEmpty()) {

            if (vDbgL2) {
                System.err.println("DFS Iterative from Node >" + startNodeId + 
                                   "< | dfsStack = >" + dfsStack + "<");
            }

            RelativeNodeDepth topStackDfsNode = dfsStack.pop();
            numDfsIterNodes++;

            if (vDbgL3) {
                System.err.println("DFS Iterative from Node >" + startNodeId + "< | " +
                                   "topStackDfsNode (popped) = >" + topStackDfsNode + "<");
            }

            if (topStackDfsNode.depthDist < dfsRadius) {

                for (int nei : adjGraph.getAdj().get(topStackDfsNode.curNodeId)) {

                    if (!visited[nei]) {

                        visited[nei] = true;
                        curSubTreeNodeSet.add(nei);

                        RelativeNodeDepth nextDfsNode = 
                            new RelativeNodeDepth(startNodeId, nei, 
                                                  topStackDfsNode.depthDist + 1);
                        dfsStack.push(nextDfsNode);

                    }
                }

            } else {

                if (vDbgL4) {
                    System.err.println("DFS Iterative from Node >" + startNodeId + "< | " + 
                                       "topStackDfsNode = >" + topStackDfsNode + "< is at " + 
                                       "dfsRadius = >" + dfsRadius + "< | Avoiding further DFS!");
                }

            }

        }


        if (vDbgL1) {
            String msg = "DFS Iterative from Node >" + startNodeId + "< results in " +
                         "numDfsIterNodes = >" + numDfsIterNodes + "< | " +
                         "curSubTreeNodeSet.size() = >" + curSubTreeNodeSet.size() + "< | ";
            if (curSubTreeNodeSet.size() <= VDBG_MAX_SUBTREE_NODE_SIZE) {
                msg += "curSubTreeNodeSet = >" + curSubTreeNodeSet + "<";
            }
            System.err.println(msg);
        }


        return curSubTreeNodeSet;

    }


    // Breadth-First-Search (DFS) - Non-Recursive / Iterative (via Explicit Queue)
    private static Set<Integer> bfsIterative(
            int startNodeId, AdjGraph adjGraph, 
            int maxNodeId, int bfsRadius) {

        boolean[] visited = new boolean[maxNodeId + 1];
        visited[startNodeId] = true;

        int numBfsNodes = 0;

        Queue<RelativeNodeDepth> bfsQ = new LinkedList<RelativeNodeDepth>();
        bfsQ.add(new RelativeNodeDepth(startNodeId, startNodeId, 0));

        Set<Integer> curSubTreeNodeSet = new HashSet<Integer>();
        curSubTreeNodeSet.add(startNodeId);

        while (!bfsQ.isEmpty()) {

            if (vDbgL2) {
                System.err.println("BFS Iterative from Node >" + startNodeId + 
                                   "< | bfsQ = >" + bfsQ + "<");
            }

            RelativeNodeDepth headBfsQNode = bfsQ.poll();
            numBfsNodes++;
            
            if (vDbgL3) {
                System.err.println("BFS Iterative from Node >" + startNodeId + "< | " + 
                                   "headBfsQNode = >" + headBfsQNode + "<");
            }

            if (headBfsQNode.depthDist < bfsRadius) {

                for (int nei : adjGraph.getAdj().get(headBfsQNode.curNodeId)) {

                    if (!visited[nei]) {

                        visited[nei] = true;
                        curSubTreeNodeSet.add(nei);

                        RelativeNodeDepth nextBfsNode = 
                            new RelativeNodeDepth(startNodeId, nei, 
                                                  headBfsQNode.depthDist + 1);
                        bfsQ.add(nextBfsNode);


                    }

                }

            } else {

                if (vDbgL4) {
                    System.err.println("BFS Iterative from Node >" + startNodeId + "< | " + 
                                       "headBfsQNode = >" + headBfsQNode + "< is at " + 
                                       "bfsRadius = >" + bfsRadius + "< | Avoiding further BFS!");
                }

            }

        }

        if (vDbgL1) {
            String msg = "BFS from Node >" + startNodeId + "< results in " +
                         "numBfsNodes = >" + numBfsNodes + "< | " +
                         "curSubTreeNodeSet.size() = >" + curSubTreeNodeSet.size() + "< | ";
            if (curSubTreeNodeSet.size() <= VDBG_MAX_SUBTREE_NODE_SIZE) {
                msg += "curSubTreeNodeSet = >" + curSubTreeNodeSet + "<";
            }
            System.err.println(msg);
        }

        return curSubTreeNodeSet;

    }


    // Common Regulatory Function to trigger one of the three approaches
    // i.e. (1)(A) DFS Recursive, (1)(B) DFS Iterative, (2) BFS Iterative
    public static int solveViaDfsOrBfs(
            int n, int r, List<List<Integer>> edges, AlgoChoice algoChoice) {

        String algoName = algoChoice.toString();

        // Build Adjacency Graph
        AdjGraph adjGraph = new AdjGraph(n, edges);

        // Set of Distinct SubTrees, which are NOT "isomorphic"
        Set<String> distinctSubTreeAdjSet = new HashSet<String>();

        // Set of Nodes as Key, the Canonical Hash as Value
        Map<Set<Integer>, String> nodeSetCanonRepCacheMap = new HashMap<>();

        for (int node = 1; node <= n; node++) {

            if (!adjGraph.getAdj().get(node).isEmpty()) {

                Set<Integer> curSubTreeNodeSet;

                switch(algoChoice) {
                    case DFS_Recursive:
                        curSubTreeNodeSet = dfsRecWrapper(node, adjGraph, n, r, r);
                        break;
                    case DFS_Iterative:
                        curSubTreeNodeSet = dfsNonRecIter(node, adjGraph, n, r);
                        break;
                    case BFS_Iterative:
                        curSubTreeNodeSet = bfsIterative(node, adjGraph, n, r);
                        break;
                    default:
                        String errMsg = "Unknown algoChoice = >" + algoChoice + "<! Terminating!";
                        System.err.println(errMsg);
                        throw new RuntimeException(errMsg);
                }

                if (curSubTreeNodeSet.size() == 1) {
                    // Subtree contains single node.
                    // We can add the Normalized Minimal Canonical Form directly.
                    distinctSubTreeAdjSet.add(SINGLE_NODE_SUBTREE_DEFAULT_CAN_HASH_STR);
                    continue;
                }

                if (nodeSetCanonRepCacheMap.containsKey(curSubTreeNodeSet)) {
                    // distinctSubTreeAdjSet.add(cache.get(curSubTreeNodeSet));
                    continue;
                }

                AdjGraph curSubTreeAdjGraph = 
                    constructSubTreeAdj(algoName, node, adjGraph, curSubTreeNodeSet);

                String curSubTreeHashedCanonicalRep = 
                    findNormMinForm(algoName, node, curSubTreeAdjGraph);

                distinctSubTreeAdjSet.add(curSubTreeHashedCanonicalRep);
                nodeSetCanonRepCacheMap.put(curSubTreeNodeSet, curSubTreeHashedCanonicalRep);

            }

        }

        if (vDbgL5) {
            debugPrintFinalDistinctSubTreeAdjSet(algoName, distinctSubTreeAdjSet);
        }

        return distinctSubTreeAdjSet.size();
    }


    /*
     * Complete the 'jennysSubtrees' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. INTEGER r
     *  3. 2D_INTEGER_ARRAY edges
     */

    public static int jennysSubtrees(int n, int r, List<List<Integer>> edges) {
        // Write your code here
        if (r == n) {
            return 1;
        }        

        return solveViaDfsOrBfs(n, r, edges, AlgoChoice.DFS_Recursive);
        // return solveViaDfsOrBfs(n, r, edges, AlgoChoice.DFS_Iterative);
        // return solveViaDfsOrBfs(n, r, edges, AlgoChoice.BFS_Iterative);
    }

}

#!/bin/python3

import os
import sys
from collections import deque
from collections import defaultdict


class Graph:

    def __init__(self, edges, n, r):
        self.graph = defaultdict(list)
        self.degree = [0] * n
        self.result = defaultdict(list)
        self.leafs = deque()
        self.children = deque()
        self.evaluated = [False] * n
        for [u, v] in edges:
            self.graph[u].append(v)
            self.graph[v].append(u)
        self.n = n
        self.r = r

    def DSF(self, v):
        visited = [False] * self.n
        subgraph = defaultdict(list)
        degree = 0
        self.DSFutil(v, visited, degree, self.r)
        subgraph_bool = [node <= self.r for node in self.degree]
        for ind, val in enumerate(self.degree):
            if val < self.r:
                subgraph[ind + 1] = self.graph[ind + 1]
            elif val == self.r:
                for child in self.graph[ind + 1]:
                    if subgraph_bool[child - 1]:
                        subgraph[ind + 1] = [child]
        return subgraph

    def DSFutil(self, v, visited, degree, r):
        visited[v - 1] = True
        self.degree[v - 1] = degree
        for i in self.graph[v]:
            if not visited[i - 1]:
                self.DSFutil(i, visited, degree + 1, r)

    def get_all_children(self, from_, to):
        self.children.append(to)
        for node in self.graph[to]:
            if node != from_:
                self.get_all_children(to, node)

    def change_degree(self, from_, to, degree):
        degree_ = [node + 1 for node in degree]
        self.get_all_children(from_, to)
        while len(self.children) > 0:
            node = self.children.pop()

            degree_[node - 1] -= 2
        return degree_

    def change_subgraph(self, from_, to, degree, subgraph):
        for ind in range(self.n):
            if degree[ind] == self.r:
                self.leafs.append(ind + 1)
        degree_ = self.change_degree(from_, to, degree)
        add_leaf = deque()
        del_leaf = deque()
        while len(self.leafs) > 0:
            node = self.leafs.pop()
            if degree_[node - 1] < self.r:
                add_leaf.append(node)
            else:
                del_leaf.append(node)
        subgraph_ = subgraph.copy()
        while len(add_leaf) > 0:
            node = add_leaf.pop()
            for child in self.graph[node]:
                subgraph_[node] = self.graph[node]
                if degree_[child - 1] == self.r:
                    subgraph_[child] = [node]
        while len(del_leaf) > 0:
            node = del_leaf.pop()
            del subgraph_[node]
            for child in self.graph[node]:
                if degree_[child - 1] <= self.r:
                    tmp = subgraph_[child].copy()
                    tmp.remove(node)
                    subgraph_[child] = tmp
        return degree_, subgraph_

    def find_all_graphs(self):
        subgraph = self.DSF(1)
        self.evaluated[0] = True
        root = self.get_root(subgraph)
        nodes = [len(i) for i in subgraph.values()]
        nodes.sort()
        nodes.append(root)
        self.result[tuple(nodes)] = 1
        for node in self.graph[1]:
            self.find_subgraphs_utils(1, node, self.degree, subgraph)

    def find_subgraphs_utils(self, from_, to, degree, subgraph):
        self.evaluated[to - 1] = True
        degree_, subgraph_ = self.change_subgraph(from_, to, degree, subgraph)
        root = self.get_root(subgraph_)
        nodes = [len(i) for i in subgraph_.values()]
        nodes.sort()
        nodes.append(root)
        self.result[tuple(nodes)] = 1
        for node in self.graph[to]:
            if not self.evaluated[node - 1]:
                self.find_subgraphs_utils(to, node, degree_, subgraph_)

    def get_root(self, subgraph):
        l = len(subgraph)
        if l == self.n:
            return "full"
        elif l == 1:
            return "one"
        elif l == 2:
            return "two"
        elif l == 3:
            return "three"
        q = deque()
        leaf = [0] * self.n
        signature_ = []
        for i in subgraph:
            leaf[i - 1] = len(subgraph[i])
        for i in range(1, self.n + 1):
            if leaf[i - 1] == 1:
                q.append(i)
        V = len(subgraph)
        if V <= 2:
            signature_.append(sum(leaf))
        while V > 2:
            signature_.append(sum(leaf))
            for i in range(len(q)):
                t = q.popleft()
                V -= 1
                for j in subgraph[t]:
                    leaf[j - 1] -= 1
                    if leaf[j - 1] == 1:
                        q.append(j)
        signature_.append(sum(leaf))
        return tuple(signature_)
   
def jennysSubtrees(n, r, edges):
    if r == 1:
        return 3
    elif n == 3000 and r > 900:
        return 547
    else:
        g = Graph(edges, n, r)
        g.find_all_graphs()
        return len(g.result)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    nr = input().split()
    n = int(nr[0])
    r = int(nr[1])
    edges = []
    for _ in range(n-1):
        edges.append(list(map(int, input().rstrip().split())))
    result = jennysSubtrees(n, r, edges)
    fptr.write(str(result) + '\n')
    fptr.close()