A

#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<pair<int,int>> ask(q+1, {-888,-888});
    vector<string> tp(q+1);
    vector<int> ans(q+1, -999);
    vector<int> seen(n+1); // {id}
    vector<int> is_key(n+1); // {id}
    vector<int> keys_in_subtree(n+1); // {id}
    vector<pair<vector<pair<int,int>>,int>> adj(n+1); // {{length,to}, id}
    int id = 0;
    auto go = [&] (auto f, int tl, int tr, vector<Edge> edges) -> void {
        id += 1;
        int tm = (tl + tr) >> 1;
        for (int i = tl; i <= tr; i += 1) {
            if (tp[i] != "get_path") {
                continue;
            }
            adj[ask[i].first].first.clear();
            adj[ask[i].second].first.clear();
            is_key[ask[i].first] = id, is_key[ask[i].second] = 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 != id) {
                    adj[u].second = id;
                    adj[u].first.clear();
                }adj[u].first.push_back({length, v});
                if (adj[v].second != id) {
                    adj[v].second = id;
                    adj[v].first.clear();
                }adj[v].first.push_back({length, u});
            } else {
                is_key[u] = id;
                is_key[v] = 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] = id;
            bool ret = is_key[u] == id;
            for (const auto &x : adj[u].first) {
                if (x.second != p) {
                    ret |= f(f, x.second, u);
                }
            }
            if (ret) {
                keys_in_subtree[u] = id;
            }
            return ret;
        };
        vector<int> roots;
        for (const auto &x : start_from) {
            if (seen[x] != id) {
                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] == 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] == 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] != "get_path") {
                return;
            }
            auto [u, v] = ask[tl];
            queue<pair<int,int>> qu; qu.push({0, u}); seen[u] = ++id;
            while (qu.size()) {
                auto [dist_tp, v_tp] = qu.front();
                qu.pop();
                if (v_tp == v) {
                    ans[tl] = dist_tp;
                    return;
                }
                for (const auto &[dist, dest] : adj[v_tp].first) {
                    if (seen[dest] != id) {
                        seen[dest] = id;
                        qu.push({dist_tp+dist, dest});
                    }
                }
            }
            ans[tl] = -1;
            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] == "get_path") {
            auto &[u, v] = ask[ii];
            cin >> u >> v;
        }
    }
    {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] == "get_path") {
            cout << ans[i] << "\n";
        }
    }
}