/////////////////////////////////////////////////////////////////////////////////////////////
// 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);
    }

}