poor euler tour tree

/*

 ∧＿∧
( ･ω･｡)つ━☆・*。
⊂　 ノ 　　　・゜
しーＪ　　 Accepted

*/



// #pragma GCC optimize("O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define all(x) begin(x), end(x)
#define x first
#define y second
// #define int long long

using namespace std;
using namespace __gnu_pbds;

typedef long double ld;
template<typename T>
using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ld PI = atan2(0, -1);

void seriy() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(14);
    #ifdef _offline
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

const int MAXN = 1e6 + 10;
const int MAXM = 600;
const int INF = 1e18;
const int BASE = 47;
const int MOD = 1e9 + 7;
const int MAXLOG = 21;

mt19937 rr(time(0));

struct treap {
    treap *left = nullptr;
    treap *right = nullptr;
    treap *parent = nullptr;
    int prior, sz, val;
    bool reversed = 0, cycle = 0;

    treap(int val) {
        this->val = val;
        this->prior = rr();
        this->sz = 1;
    }
};

vector<vector<int>> g;
vector<treap*> links;


int get_size(treap *&root) {
    return ((root == nullptr) ? 0 : root->sz);
}

int get_val(treap *&root) {
    return ((root == nullptr) ? -1 : root->val);
}

int get_rev(treap *&root) {
    return ((root == nullptr) ? -1 : root->reversed);
}

void print(treap *a) {
    if(a->left != nullptr) print(a->left);
    cerr << get_val(a) << " " << get_rev(a) << " " << get_val(a->left) << " " << get_val(a->right) << '\n';
    if(a->right != nullptr) print(a->right);
}

void update(treap *&root) {
    if(root == nullptr) return;
    root->sz = get_size(root->left) + get_size(root->right) + 1;
    if(root->left != nullptr) {
        root->left->parent = root;
    }
    if(root->right != nullptr) {
        root->right->parent = root;
    }
}

void push(treap *&root) {
    if(root == nullptr || root->reversed == 0) {
        return;
    }
    if(root->left != nullptr) {
        root->left->reversed ^= 1;
    }
    if(root->right != nullptr) {
        root->right->reversed ^= 1;
    }
    swap(root->left, root->right);
    root->reversed = 0;
}

pair<treap*, treap*> split(treap *&root, int key) {
    push(root);
    if(root == nullptr) {
        return {nullptr, nullptr};
    }
    int root_key = get_size(root->left);
    // cerr << root->sz << " " << root_key << '\n';
    if(key > root_key) {
        pair<treap*, treap*> splitted = split(root->right, key - get_size(root->left) - 1);
        root->right = splitted.x;
        update(root);
        return {root, splitted.y};
    }
    else {
        pair<treap*, treap*> splitted = split(root->left, key);
        root->left = splitted.y;
        update(root);
        return {splitted.x, root};
    }
}

treap* merge(treap *&left, treap *&right) {
    push(left);
    push(right);
    if(left == nullptr) {
        return right;
    }
    if(right == nullptr) {
        return left;
    }
    if(left->prior > right->prior) {
        left->right = merge(left->right, right);
        update(left);
        return left;
    }
    else {
        right->left = merge(left, right->left);
        update(right);
        return right;
    }
}

treap* get(treap *&root, int pos) {
    push(root);
    if(pos < get_size(root->left)) {
        return get(root->left, pos);
    }
    else if(pos > get_size(root->left)) {
        return get(root->right, pos - get_size(root->left) - 1);
    }
    else {
        return root;
    }
}

void reverse(treap *&root, int l, int r) {
    pair<treap*, treap*> a = split(root, r);
    pair<treap*, treap*> b = split(a.x, l);
    b.y->reversed ^= 1;
    b.x = merge(b.x, b.y);
    root = merge(b.x, a.y);
}

void insert(treap *&root, int pos, int val) {
    pair<treap*, treap*> splitted = split(root, pos);
    treap *nw = new treap(val);
    splitted.x = merge(splitted.x, nw);
    update(splitted.x);
    splitted.x = merge(splitted.x, splitted.y);
    update(splitted.x);
    root = splitted.x;
}

vector<vector<int>> bamboos, cycles;
vector<bool> used;
vector<int> cur;
bool is_cyc = 0;

void dfs(int u) {
    used[u] = 1;
    cur.push_back(u);
    for(auto v : g[u]) {
        if(!used[v]) {
            dfs(v);
        }
        else {
            is_cyc = 1;
        }
    }
}

vector<int> where;

treap* get_root(treap *&a) {
    if(a->parent == nullptr) {
        return a;
    }
    return get_root(a->parent);
}

treap* get_root2(treap *&a) {
    if(a->parent == nullptr) {
        return a;
    }
    if(a->parent->right == a) {
        where.push_back(1);
    }
    else {
        where.push_back(-1);
    }
    return get_root2(a->parent);
}

void recalc(treap *&a, int cur) {
    if(a->reversed) {
        cur *= -1;
    }
    push(a);
    // cerr << get_val(a) << '\n';
    if(where.size() == 0) {
        return;
    }
    int back = where.back() * cur;
    where.pop_back();
    if(back > 0) {
        recalc(a->right, 1);
    }
    else {
        recalc(a->left, 1);
    }
}

int get_pos(treap *&a) {
    if(a == nullptr) {
        return 0;
    }
    // cerr << a->val << " ";
    int ans = 0;
    if(a->parent != nullptr && a->parent->right == a) {
        ans += get_size(a->parent->left) + 1;
    }
    return ans + get_pos(a->parent);
}

treap* lefter(treap *&a) {
    push(a);
    if(a->left == nullptr) {
        return a;
    }
    return lefter(a->left);
}

treap* righter(treap *&a) {
    push(a);
    if(a->right == nullptr) {
        return a;
    }
    return righter(a->right);
}

signed main() {
    seriy();
    int n, m, q;
    cin >> n >> m >> q;
    g.resize(n);
    used.resize(n);
    links.resize(n);
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 0; i < n; i++) {
        if(!used[i] && g[i].size() <= 1) {
            cur.clear();
            dfs(i);
            bamboos.push_back(cur);
        }
    }
    for(int i = 0; i < n; i++) {
        if(!used[i]) {
            cur.clear();
            dfs(i);
            cycles.push_back(cur);
        }
    }
    for(int i = 0; i < bamboos.size(); i++) {
        treap *start = nullptr;
        for(int j = 0; j < bamboos[i].size(); j++) {
            int cur = bamboos[i][j];
            insert(start, j, cur);
            links[bamboos[i][j]] = get(start, j);
        }
    }

    // for(int i = 0; i < bamboos.size(); i++) {
    //     for(auto j : bamboos[i]) {
    //         cerr << j << " " << get_val(links[j]->parent) << '\n';
    //     }
    //     cerr << '\n';
    // }

    for(int i = 0; i < cycles.size(); i++) {
        treap *start = nullptr;
        for(int j = 0; j < cycles[i].size(); j++) {
            int cur = cycles[i][j];
            insert(start, j, cur);
            links[cycles[i][j]] = get(start, j);
        }
        treap *root = get_root(links[cycles[i][0]]);
        root->cycle = 1;
    }

    // for(int i = 0; i < cycles.size(); i++) {
    //     for(auto j : cycles[i]) {
    //         cerr << j << " " << get_val(links[j]->parent) << '\n';
    //     }
    //     cerr << '\n';
    // }

    // cerr << '\n';
    while(q--) {
        char c;
        cin >> c;
        if(c == '?') {
            int a, b;
            cin >> a >> b;
            a--;
            b--;
            treap *r1 = get_root2(links[a]);
            recalc(r1, 1);
            treap *r2 = get_root2(links[b]);
            // print(r2);
            // cerr << '\n';
            // for(auto i : where) {
            //     cerr << i << " ";
            // }
            // cerr << '\n';
            // cerr << 1;
            recalc(r2, 1);
            if(r1 == r2) {
                // print(r1);
                // cerr << '\n';
                int p1 = get_pos(links[a]) + get_size(links[a]->left);
                int p2 = get_pos(links[b]) + get_size(links[b]->left);
                if(p2 < p1) {
                    swap(p1, p2);
                }
                // cerr << p1 << " " << p2 << '\n';
                int ans;
                treap *root = get_root(links[a]);
                if(root->cycle) {
                    ans = min(p2 - p1, p1 + get_size(root) - p2);
                }
                else {
                    ans = p2 - p1;
                }
                cout << max(ans - 1, 0) << '\n';
            }
            else {
                cout << -1 << '\n';
            }
        }
        else if(c == '+') {
            int a, b;
            cin >> a >> b;
            a--;
            b--;
            treap *root1 = get_root2(links[a]);
            recalc(root1, 1);
            treap *root2 = get_root2(links[b]);
            recalc(root2, 1);

            if(root1 != root2) {
                treap *left1 = lefter(root1);
                treap *right1 = righter(root1);
                treap *left2 = lefter(root2);
                treap *right2 = righter(root2);
                // print(root1);
                // cerr << '\n';

                if(get_val(right1) != a) {
                    reverse(root1, -1, get_size(root1));
                }
                if(get_val(left2) != b) {
                    reverse(root2, -1, get_size(root2));
                }

                // print(root1);
                // cerr << '\n';
                root1 = merge(root1, root2);
                // print(root1);
            }
            else {
                root1->cycle = 1;
            }
        }
        else if(c == '-') {
            int a, b;
            cin >> a >> b;
            a--;
            b--;
            treap *root1 = get_root2(links[a]);
            recalc(root1, 1);
            treap *root2 = get_root2(links[b]);
            recalc(root2, 1);
            int p1 = get_pos(links[a]) + get_size(links[a]->left);
            int p2 = get_pos(links[b]) + get_size(links[b]->left);
            if(p1 > p2) {
                swap(p1, p2);
            }
            if(root1->cycle) {
                treap *left = lefter(root1);
                treap *right = righter(root1);
                root1->cycle = 0;

                if(p1 > p2) {
                    swap(p1, p2);
                }
                if(get_val(left) == a && get_val(right) == b || get_val(left) == b && get_val(right) == a) {

                }
                else {
                    reverse(root1, -1, p2);
                    reverse(root1, p2, get_size(root1));
                }
            }
            else {
                pair<treap*, treap*> splitted = split(root1, p2);
                splitted.x->parent = nullptr;
                splitted.y->parent = nullptr;
            }
        }
    }
    return 0;
}