D1

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int INF = 1e18;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    struct Edge {
        int u, v, ql, qr, length;
    };
    struct Vertex {
        int u, ql, qr, color;
    };
    struct VertexValues /* These values are shared across whole segment (t=l..r), these values get relaxed in different segtree nodes */ {
        int u, dist_to_blue, dist_to_red;
    };
    int n, q;
    cin >> n >> q;
    vector<int> ask(q+1, -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<pair<int,int>> vvs(n+1); // {dist_to_blue, dist_to_red}
    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, tuple<vector<Edge>,vector<Vertex>,vector<VertexValues>> G) -> void {
        dfs_id += 1;
        int tm = (tl + tr) >> 1;
        for (int i = tl; i <= tr; i += 1) {
            if (tp[i] == "link" || tp[i] == "cut") {
                continue;
            }
            is_key[ask[i]] = dfs_id;
        }
        vector<Edge> etol, etor;
        vector<int> start_from;
        for (const auto &[u, v, l, r, length] : get<0>(G)) {
            if (l<=tl&&tr<=r) {
                start_from.push_back(u), start_from.push_back(v);
                vvs[u] = vvs[v] = {(int)INF, (int)INF};
                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) {
                    etol.push_back({u,v,l,min(r,tm),length});
                }
                if (r >= tm+1) {
                    etor.push_back({u,v,max(l, tm+1),r,length});
                }
            }
        }
        for (const auto &[u, b, r] : get<2>(G)) {
            vvs[u] = {b, r};
        }
        for (const auto &[u, l, r, co] : get<1>(G)) {
            if (l<=tl&&tr<=r) {
                if (co == 0) {
                    vvs[u].first = min(vvs[u].first, 0ll);
                }
                if (co == 1) {
                    vvs[u].second = min(vvs[u].second, 0ll);
                }
            } else {
                is_key[u] = dfs_id;
            }
        }
        vector<Vertex> vtol, vtor;
        for (const auto &[u, l, r, co] : get<1>(G)) {
            if (is_key[u] == dfs_id) {
                if (l <= tm) {
                    vtol.push_back({u,l,min(r,tm),co});
                }
                if (r >= tm+1) {
                    vtor.push_back({u,max(l, tm+1),r,co});
                }
            }
        }
        vector<vector<tuple<int,int,int>>> dfs_tree_layers(start_from.size());
        auto find_keys = [&] (auto f, int u, int p, int l) -> bool {
            seen[u] = dfs_id;
            bool ret = is_key[u] == dfs_id;
            for (const auto &x : adj[u].first) {
                if (x.second != p) {
                    dfs_tree_layers[l].push_back({x.first, u, x.second});
                    ret |= f(f, x.second, u, l+1);
                }
            }
            if (ret) {
                keys_in_subtree[u] = dfs_id;
            }
            return ret;
        };
        vector<int> roots;
        for (const auto &x : start_from) {
            if (seen[x] != dfs_id) {
                find_keys(find_keys, x, -1, 0);
                roots.push_back(x);
            }
        }
        vector<tuple<int,int,int>> layers_order;
        for (const auto &x : dfs_tree_layers) {
            for (const auto &y : x) {
                layers_order.push_back(y);
            }
        }
        for (int i = 0; i < 2; i += 1) {
            reverse(layers_order.begin(), layers_order.end());
            for (auto &[l, from, to] : layers_order) {
                swap(from, to);
            }
            for (const auto &[l, from, to] : layers_order) {
                vvs[to].first = min(vvs[to].first, vvs[from].first+l);
                vvs[to].second = min(vvs[to].second, vvs[from].second+l);
            }
        }
        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) {
                    etol.push_back({dest, u, tl, tm, l});
                    etor.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_blue") {
                ans[tl] = vvs[ask[tl]].first == INF ? -1 : vvs[ask[tl]].first;
            }
            if (tp[tl] == "get_red") {
                ans[tl] = vvs[ask[tl]].second == INF ? -1 : vvs[ask[tl]].second;
            }
            return;
        }
        vector<VertexValues> vvs_pass_down;
        for (const auto &[u, l, r, co] : get<1>(G)) {
            if (is_key[u] == dfs_id) {
                vvs_pass_down.push_back({u, vvs[u].first, vvs[u].second});
            }
        }
        f(f, tl, tm, {etol, vtol, vvs_pass_down});
        f(f, tm+1, tr, {etor, vtor, vvs_pass_down});
    };
    vector<Edge> edges(q+1, {-1,-1,-1,-1,-1});
    vector<Vertex> vertices;
    vector<int> last(n+1); for (int i = 1; i <= n; i += 1) last[i] = i-1, vertices.push_back({i, 1, q, 0});
    for (int ii = 1; ii <= q; ii += 1) {
        cin >> tp[ii];
        if (tp[ii] == "link") {
            cin >> edges[ii].u >> edges[ii].v >> edges[ii].length;
            edges[ii].ql = ii;
            edges[ii].qr = q;
        }
        if (tp[ii] == "cut") {
            int i;
            cin >> i;
            edges[i].qr = ii-1;
        }
        if (tp[ii] == "make_blue") {
            cin >> ask[ii];
            if (last[ask[ii]] != -1) {
                vertices[last[ask[ii]]].qr = ii-1;
            }last[ask[ii]] = vertices.size(); vertices.push_back({ask[ii], ii, q, 0});
        }
        if (tp[ii] == "make_red") {
            cin >> ask[ii];
            if (last[ask[ii]] != -1) {
                vertices[last[ask[ii]]].qr = ii-1;
            }last[ask[ii]] = vertices.size(); vertices.push_back({ask[ii], ii, q, 1});
        }
        if (tp[ii] == "get_blue") {
            cin >> ask[ii];
        }
        if (tp[ii] == "get_red") {
            cin >> ask[ii];
        }
    }
    {vector<Edge> nw;for(int ii = 1; ii <= q; ii += 1)if(tp[ii] == "link")nw.push_back(edges[ii]);edges = nw;}
    vector<VertexValues> vv; for (int i = 1; i <= n; i += 1) vv.push_back({i, INF, INF});
    go(go, 1, q, {edges, vertices, vv});
    for (int i = 1; i <= q; i += 1) {
        if (tp[i] == "get_red" || tp[i] == "get_blue") {
            cout << ans[i] << "\n";
        }
    }
}