class Treap {
 public:
    Treap *path_parent;
    bool rev;

    Treap() : path_parent(0), rev(false), parent(0), l(0), r(0), y(rnd()), cnt(1) {}

    Treap* get_root() {
        if (parent) {
            return parent->get_root();
        }
        return this;
    }

    int get_ord() {
        push_path();
        Treap *v = this;
        Treap *prv = v;
        int cnt = 0;
        while (v) {
            if (v->l != prv) {
                cnt += get_cnt(v->l) + 1;
            }
            prv = v;
            v = v->parent;
        }
        return cnt;
    }

    static int get_cnt(Treap*);

    static Treap* merge(Treap*, Treap*);

    static pair<Treap*, Treap*> split(Treap*, int);

 private:
    Treap *parent;
    Treap *l, *r;
    unsigned int y;
    int cnt;

    static std::mt19937 rnd;

    void push() {
        if (rev) {
            swap(l, r);
            if (l) {
                l->rev ^= 1;
            }
            if (r) {
                r->rev ^= 1;
            }
            rev = false;
        }
    }

    void set_son(Treap *&son, Treap *v) {
        son = v;
        if (v) {
            v->parent = this;
        }
        cnt = 1 + get_cnt(l) + get_cnt(r);
    }

    Treap* set_left_son(Treap *v) {
        set_son(l, v);
        return this;
    }

    Treap* set_right_son(Treap *v) {
        set_son(r, v);
        return this;
    }

    void push_path() {
        static std::vector<Treap*> path;
        Treap *v = this;
        do {
            path.push_back(v);
        } while ((v = v->parent));
        for (auto it = path.rbegin(); it != path.rend(); ++it) {
            (*it)->push();
        }
        path.clear();
    }
};

std::mt19937 Treap::rnd;

int Treap::get_cnt(Treap *t) {
    return t ? t->cnt : 0;
}

Treap* Treap::merge(Treap *a, Treap *b) {
    if (!a || !b) {
        return a ? a : b;
    }
    a->push();
    b->push();
    if (a->y < b->y) {
        return a->set_right_son(merge(a->r, b));
    } else {
        return b->set_left_son(merge(a, b->l));
    }
}

pair<Treap*, Treap*> Treap::split(Treap* t, int k) {
    if (!t) {
        return {nullptr, nullptr};
    }
    t->push();
    int left_cnt = get_cnt(t->l);
    pair<Treap*, Treap*> res;
    if (k <= left_cnt) {
        res = split(t->l, k);
        res.second = t->set_left_son(res.second);
    } else {
        res = split(t->r, k - left_cnt - 1);
        res.first = t->set_right_son(res.first);
    }
    if (res.first) {
        res.first->parent = 0;
    }
    if (res.second) {
        res.second->parent = 0;
    }
    return res;
}

class LinkCut {
 public:
    explicit LinkCut(int n) {
        vertex.resize(n);
        for (int i = 0; i < n; i++) {
            vertex[i] = new Treap();
        }
    }

    void link(int u, int v) {
        link(vertex[u], vertex[v]);
    }

    void cut(int u, int v) {
        cut(vertex[u], vertex[v]);
    }

    int get(int u, int v) {
        return get(vertex[u], vertex[v]);
    }

 private:
    vector<Treap*> vertex;

    Treap* expose(Treap *v) {
        Treap *partial_path = 0;
        while (v) {
            Treap *cur_path = v->get_root();
            Treap *next_v = cur_path->path_parent;
            cur_path->path_parent = 0;
            auto [upper_part, lower_part] = Treap::split(cur_path, v->get_ord());
            if (lower_part) {
                lower_part->path_parent = v;
            }
            partial_path = Treap::merge(upper_part, partial_path);
            v = next_v;
        }
        return partial_path;
    }

    Treap* make_root(Treap *v) {
        Treap *path = expose(v);
        path->rev ^= 1;
        return path;
    }

    void link(Treap *u, Treap *v) {
        make_root(u)->path_parent = v;
    }

    void cut(Treap *u, Treap *v) {
        make_root(u);
        Treap *path = expose(v);
        Treap::split(path, v->get_ord() - 1);
    }

    int get(Treap *u, Treap *v) {
        make_root(u);
        int result = Treap::get_cnt(expose(v));
        return (u->get_root() == v->get_root()) ? (result - 1) : -1;
    }
};