#include <bits/stdc++.h>
using namespace std;
const int NMAX=1e5;
struct lct {
    struct node {
        int child[2];
        int sum, rev_tag, parent, value;
    };
    node tree[NMAX+5];
    void push(int node) {
        if (tree[node].rev_tag==0) return;
        swap(tree[node].child[0], tree[node].child[1]);
        if (tree[node].child[0]) tree[tree[node].child[0]].rev_tag^=1;
        if (tree[node].child[1]) tree[tree[node].child[1]].rev_tag^=1;
        tree[node].rev_tag=0;
    }
    void pull(int node) {
        tree[node].sum=tree[node].value;
        if (tree[node].child[0]) tree[node].sum+=tree[tree[node].child[0]].sum;
        if (tree[node].child[1]) tree[node].sum+=tree[tree[node].child[1]].sum;
    }
    int get(int node) {
        if (!tree[node].parent) return -1;
        if (node==tree[tree[node].parent].child[0]) return 0;
        if (node==tree[tree[node].parent].child[1]) return 1;
        return -1;
    }
    void rotate(int node) {
        int p = tree[node].parent;
        int pp = tree[p].parent;
        int side1 = get(node);
        int side2 = get(p);
        tree[p].child[side1] = tree[node].child[side1 ^ 1];
        if (tree[p].child[side1]) {
            tree[tree[p].child[side1]].parent = p;
        }
        tree[node].child[side1 ^ 1] = p;
        tree[p].parent = node;
        tree[node].parent = pp;
        if (side2 != -1) tree[pp].child[side2] = node;
        pull(p);
        pull(node);
    }
    void propagate(int node) {
        if (get(node)!=-1) propagate(tree[node].parent);
        push(node);
    }
    void splay(int node) {
        propagate(node);
        while (get(node)!=-1) {
            int side1=get(node);
            int side2=get(tree[node].parent);
            if (side2!=-1) {
                if (side1==side2) {
                    rotate(tree[node].parent);
                }else {
                    rotate(node);
                }
            }
            rotate(node);
        }
    }
    int access(int node) {
        int last=0;
        for (int cur=node;cur;last=cur, cur=tree[cur].parent) {
            splay(cur);
            tree[cur].child[1]=last;
            pull(cur);
        }
        splay(node);
        return last;
    }
    void make_root(int node) {
        access(node);
        tree[node].rev_tag^=1;
    }
    int find_root(int node) {
        access(node);
        while (tree[node].child[0]) {
            push(node);
            node=tree[node].child[0];
        }
        splay(node);
        return node;
    }
    void link_unrooted(int u, int v) {
        if (find_root(u)==find_root(v)) return;
        make_root(u);
        tree[u].parent=v;
    }
    void link_rooted(int u, int v) {
        access(u);
        tree[u].parent = v;
    }
    void cut_unrooted(int u, int v) {
        if (find_root(u)!=find_root(v)) return;
        make_root(u);
        access(v);
        if (tree[v].child[0]==u) {
            tree[v].child[0]=0;
            tree[u].parent=0;
            pull(v);
        }
    }
    void cut_rooted(int u, int v) {
        access(u);
        if (tree[u].child[0]) {
            tree[tree[u].child[0]].parent = 0;
            tree[u].child[0] = 0;
            pull(u);
        }
    }
    int lca(int u, int v) {
        access(u);
        return access(v);
    }
};
lct tree;
int main() {
    int n, m;
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        string s;
        cin>>s;
        if (s=="lca") {
            int a, b;
            cin>>a>>b;
            cout<<tree.lca(a, b)<<'\n';
        }else if (s=="link") {
            int a, b;
            cin>>a>>b;
            tree.link_rooted(a,b);
        }else {
            int a;
            cin>>a;
            tree.access(a);
            int p=tree.tree[a].child[0];
            if (p) {
                tree.push(p);
                while (tree.tree[p].child[1]) {
                    p=tree.tree[p].child[1];
                    tree.push(p);
                }
                tree.cut_rooted(a, p);
            }
        }
    }
}