C

#include <bits/stdc++.h>
using namespace std;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    struct Edge {
        int u, v, ql, qr, length;
    };
    int n, q;
    cin >> n >> q;
    vector<array<int,3>> ask(q+1, {-888,-888,-888});
    vector<string> tp(q+1);
    vector<int> ans(q+1, -999);
    vector<int> seen(n+1); // {dfs_id}
    vector<int> is_key(n+1); // {dfs_id}
    vector<int> keys_in_subtree(n+1); // {dfs_id}
    vector<int> up(n+1);
    auto LCA = [&] (int u, int v) -> int {
        vector<int> up_u = {u}; while (up[u]) up_u.push_back(u = up[u]);
        vector<int> up_v = {v}; while (up[v]) up_v.push_back(v = up[v]);
        int ret = -1;
        while (up_u.size() && up_v.size() && up_u.back() == up_v.back()) {
            ret = up_u.back();
            up_u.pop_back(), up_v.pop_back();
        }
        return ret;
    };
    vector<pair<vector<pair<int,int>>,int>> adj(n+1); // {{length,to}, dfs_id}
    int dfs_id = 0;
    auto go = [&] (auto f, int tl, int tr, vector<Edge> edges) -> void {
        dfs_id += 1;
        int tm = (tl + tr) >> 1;
        for (int i = tl; i <= tr; i += 1) {
            if (tp[i] != "lca") {
                continue;
            }
            for (const auto &x : ask[i]) {
                up[x] = 0;
                is_key[x] = dfs_id;
            }
        }
        vector<Edge> to_l, to_r;
        vector<int> start_from;
        for (const auto &[u, v, l, r, length] : edges) {
            if (l<=tl&&tr<=r) {
                start_from.push_back(u);
                start_from.push_back(v);
                if (adj[u].second != dfs_id) {
                    adj[u].second = dfs_id;
                    adj[u].first.clear();
                }adj[u].first.push_back({length, v});
                if (adj[v].second != dfs_id) {
                    adj[v].second = dfs_id;
                    adj[v].first.clear();
                }adj[v].first.push_back({length, u});
            } else {
                is_key[u] = dfs_id;
                is_key[v] = dfs_id;
                if (l <= tm) {
                    to_l.push_back({u,v,l,min(r,tm),length});
                }
                if (r >= tm+1) {
                    to_r.push_back({u,v,max(l, tm+1),r,length});
                }
            }
        }
        auto find_keys = [&] (auto f, int u, int p) -> bool {
            seen[u] = dfs_id;
            bool ret = is_key[u] == dfs_id;
            for (const auto &x : adj[u].first) {
                if (x.second != p) {
                    up[x.second] = u;
                    ret |= f(f, x.second, u);
                }
            }
            if (ret) {
                keys_in_subtree[u] = dfs_id;
            }
            return ret;
        };
        vector<int> roots;
        for (const auto &x : start_from) {
            if (seen[x] != dfs_id) {
                up[x] = 0;
                find_keys(find_keys, x, -1);
                roots.push_back(x);
            }
        }
        auto dfs = [&] (auto f, int u, int p) -> pair<int,int> /* length, destination */ {
            vector<pair<int,int>> children;
            for (const auto &x : adj[u].first) {
                if (x.second != p && keys_in_subtree[x.second] == dfs_id) {
                    pair<int,int> z = f(f, x.second, u);
                    z.first += x.first;
                    children.push_back(z);
                }
            }
            if (children.size() > 1 || is_key[u] == dfs_id || p == -1 /* root */) {
                for (const auto &[l, dest] : children) {
                    to_l.push_back({dest, u, tl, tm, l});
                    to_r.push_back({dest, u, tm+1, tr, l});
                }
                return {0, u};
            }
            if (children.size()) {
                return children.front();
            }
            return {0, u};
        };
        for (const auto &x : roots) {
            dfs(dfs, x, -1);
        }
        if (tl == tr) {
            if (tp[tl] != "lca") {
                return;
            }
            auto [u, v, rt] = ask[tl];
            ans[tl] = 0;
            for (const auto &x : {LCA(u,v), LCA(u, rt), LCA(v, rt)}) {
                if (x == -1) {
                    ans[tl] = -1;
                    break;
                }
                ans[tl] ^= x;
            }
            return;
        }
        f(f, tl, tm, to_l);
        f(f, tm+1, tr, to_r);
    };
    vector<Edge> edges(q+1, {-1,-1,-1,-1,-1});
    for (int ii = 1; ii <= q; ii += 1) {
        cin >> tp[ii];
        if (tp[ii] == "link") {
            cin >> edges[ii].u >> edges[ii].v;
            edges[ii].ql = ii;
            edges[ii].qr = q;
            edges[ii].length = 1;
        }
        if (tp[ii] == "cut") {
            int i;
            cin >> i;
            edges[i].qr = ii-1;
        }
        if (tp[ii] == "lca") {
            auto &[u, v, root] = ask[ii];
            cin >> u >> v >> root;
        }
    }
    {vector<Edge> nw;for(int ii = 1; ii <= q; ii += 1)if(tp[ii] == "link")nw.push_back(edges[ii]);edges = nw;}
    go(go, 1, q, edges);
    for (int i = 1; i <= q; i += 1) {
        if (tp[i] == "lca") {
            cout << ans[i] << "\n";
        }
    }
}