drva 4

import java.util.HashMap;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int n = Integer.parseInt(scn.next());
        int q = Integer.parseInt(scn.next());
        BTree<String> tree = new BTree<>();
        HashMap<String, BNode<String>> map = new HashMap<>();
        for(int i = 0; i<q+n; i++){
            String command = scn.next();
            if(command.equals("root")){
                String name = scn.next();
                tree.makeRoot(name);
                map.put(name,tree.root);
            }
            else if(command.equals("add")){
                String parent = scn.next();
                String child = scn.next();
                String where = scn.next();
                BNode<String> parentNode = map.get(parent);
                BNode<String> childNode = new BNode<String>(child);
                if(where.equals("LEFT")) parentNode.left = childNode;
                else parentNode.right=childNode;
                map.put(child, childNode);
            }
            else if(command.equals("ask")){
                String node = scn.next();
                System.out.println(maxDepth(map.get(node)));
            }
        }

    }
    public static int maxDepth(BNode<String> node){
        if(node==null) return 0;
        return 1 + Math.max(maxDepth(node.left),maxDepth(node.right));
    }

}