drva 1

// Следните класи веќе се импортирани, не е дозволено копирање на класи овде, директно користејте ги како кога се достапни во други локални фајлови:
// The following classes are already imported, copying classes here is not allowed, use them directly as when they are available in other local files:

// CBHT, OBHT, MapEntry, SLLNode веќе се импортирани
// CBHT, OBHT, MapEntry, SLLNode are already imported
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;
import java.util.*;


// Овде креирајте ги помошните класи за клуч и вредност
// Исполнете ги барањата од текстот за toString методите
// Дополнително осигурете се дека вашата клуч класа ќе ги имплементира потребните
// hashCode и equals методи

// Create the helper classes for key and value here
// Fulfill the requirements from the text for the toString methods
// Additionally, make sure that your key class will implement the required
// hashCode and equals methods


public class Main {
    public static int numberOfLeaves(SLLTree<Integer> tree, Tree.Node<Integer> node, HashMap<Integer, Tree.Node<Integer>> map){
        if(node==null) return 0;

        if(tree.childCount(node)==0) return 1;
        int total = 0;
        Iterator<Integer> children = tree.children(node);

        while(children.hasNext()){
            Integer childValue = children.next();
            Tree.Node<Integer> childNode = map.get(childValue);
            total+=numberOfLeaves(tree, childNode, map);
        }
        return total;
    }
    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int n = Integer.parseInt(scn.next());
        int q = Integer.parseInt(scn.next());
        SLLTree<Integer> tree = new SLLTree<>();
        HashMap<Integer, Tree.Node<Integer>> map = new HashMap<>();
        for(int i = 0; i<q+n; i++){
            String command = scn.next();
            if(command.equals("root")){
                int index = Integer.parseInt(scn.next());
                tree.makeRoot(1);
                map.put(1,tree.root());
            }
            else if(command.equals("add")){
                int parent = Integer.parseInt(scn.next());
                int child = Integer.parseInt(scn.next());
                Tree.Node<Integer> parentNode = map.get(parent);
                Tree.Node<Integer> childNode = tree.addChild(parentNode, child);
                map.put(child, childNode);
            }
            else if(command.equals("ask")){
                int node = Integer.parseInt(scn.next());
                System.out.println(numberOfLeaves(tree, map.get(node), map));
            }
        }

    }

}