#include #include namespace nachia { struct IncrementalForest{ struct Node { int jump; int parent; int parentEdge; int depth; int child; int brother; }; std::vector nodes; std::vector dsu; std::vector todbl; int edgeIndex; void makeToDbl(int x){ while(int(todbl.size()) < x){ int z = int(todbl.size()); todbl.resize(z*2+1); std::copy(todbl.begin(), todbl.begin() + z, todbl.begin() + z); todbl[z*2] = true; } } IncrementalForest(int n = 0){ nodes.assign(n, { -1, -1, -1, 0, -1, -1 }); dsu.assign(n, -1); todbl.assign(1, false); makeToDbl(n); edgeIndex = 0; } int rootOf(int u){ if(dsu[u] < 0) return u; return dsu[u] = rootOf(dsu[u]); } bool areConnected(int u, int v){ return rootOf(u) == rootOf(v); } int componentSize(int u){ return -dsu[rootOf(u)]; } int numVertices(){ return nodes.size(); } int addNode(){ int v = numVertices(); nodes.push_back({ -1, -1, -1, 0, -1, -1 }); makeToDbl(numVertices()); return v; } int addEdge(int u, int v){ std::vector bfs; { int ru = rootOf(u); int rv = rootOf(v); if(ru == rv) return -1; if(-dsu[ru] < -dsu[rv]){ std::swap(u, v); std::swap(ru, rv); } bfs = std::vector(-dsu[rv]); dsu[ru] += dsu[rv]; dsu[rv] = ru; } int e = edgeIndex++; int bfsp = 0; auto setParent = [&](int v, int p) -> void { nodes[v].parent = p; nodes[v].depth = nodes[p].depth + 1; nodes[v].jump = todbl[nodes[v].depth - 1] ? nodes[nodes[p].jump].jump : p; }; int p = u; int p2 = v; for(int x=nodes[v].child; x>=0; x=nodes[x].brother) bfs[bfsp++] = x; while(nodes[p2].parent >= 0){ int w = nodes[p2].parent; for(int *pc=&nodes[w].child; *pc>=0; ){ int x = *pc; if(x == p2){ *pc = nodes[x].brother; std::swap(nodes[p2].parentEdge, e); nodes[p2].brother = nodes[p].child; nodes[p].child = p2; setParent(p2, p); } else { bfs[bfsp++] = x; pc = &nodes[x].brother; } } p = p2; p2 = w; } std::swap(nodes[p2].parentEdge, e); nodes[p2].brother = nodes[p].child; nodes[p].child = p2; setParent(p2, p); for(int i=0; i=0; x=nodes[x].brother) bfs[bfsp++] = x; } return edgeIndex - 1; } int parentOf(int u){ return nodes[u].parent; } int parentEdgeOf(int u){ return nodes[u].parentEdge; } int depth(int u){ return nodes[u].depth; } int lca(int u, int v){ if(!areConnected(u, v)) return -1; if(depth(u) < depth(v)) std::swap(u, v); int dv = depth(v); while(depth(u) != dv){ u = (depth(nodes[u].jump) >= dv ? nodes[u].jump : nodes[u].parent); } while(u != v){ if(nodes[u].jump != nodes[v].jump){ u = nodes[u].jump; v = nodes[v].jump; } else { u = nodes[u].parent; v = nodes[v].parent; } } return u; } int middle(int u, int v, int w){ if(!areConnected(u, v) || !areConnected(v, w)) return -1; return lca(u,v) ^ lca(v,w) ^ lca(w,u); } int dist(int u, int v){ if(!areConnected(u, v)) return -1; return depth(u) - depth(lca(u, v)) * 2 + depth(v); } struct ChildrenIterRange { struct Iter { std::vector::iterator nodes; int v; int operator*() const { return v; } Iter& operator++(){ v = nodes[v].brother; return *this; } Iter operator++(int) const { auto a = *this; return ++a; } bool operator==(Iter& r) const { return v == r.v; } bool operator!=(Iter& r) const { return v != r.v; } }; std::vector::iterator nodes; int v; Iter begin() const { return { nodes, nodes[v].child }; } Iter end() const { return { nodes, -1 }; } }; ChildrenIterRange children(int v){ return ChildrenIterRange{ nodes.begin(), v }; } }; } // namespace nachia #include #include int main(){ using namespace std; ios::sync_with_stdio(false); cin.tie(nullptr); int N, X, Q; cin >> N >> X >> Q; nachia::IncrementalForest forest(N); std::vector depth(N); std::vector weight; struct Diam { long long d; int v; int w; }; std::vector diam(N); for(int i=0; i long long { int g = forest.lca(u, v); if(g < 0) return -1; long long d = depth[u] - 2 * depth[g] + depth[v]; return d; }; auto mergeDiam = [&](Diam l, Diam r) -> Diam { Diam res = l; if(res.d < r.d) res = r; auto upd = [&](int v, int w){ long long d = dist(v,w); if(res.d < d) res = { d,v,w }; }; upd(l.v, r.v); upd(l.v, r.w); upd(l.w, r.v); upd(l.w, r.w); return res; }; for(int qi=0; qi> t; if(t == 1){ int v, w; cin >> v >> w; int u = X; int ur = forest.rootOf(u); int vr = forest.rootOf(v); if(forest.addEdge(u, v) < 0) exit(1); int xr = forest.rootOf(v); weight.push_back(w); if(forest.parentOf(v) != u) std::swap(u, v); auto dfs = [&](auto& dfs, int x) -> void { depth[x] = depth[forest.parentOf(x)] + weight[forest.parentEdgeOf(x)]; for(int y : forest.children(x)) dfs(dfs, y); }; dfs(dfs, v); diam[xr] = mergeDiam(diam[ur], diam[vr]); } if(t == 2){ int u, v; cin >> u >> v; long long d = dist(u, v); cout << d << '\n'; if(d != -1) X = (X + d) % N; } if(t == 3){ int v; cin >> v; cout << diam[forest.rootOf(v)].d << '\n'; } if(t == 4){ int v; cin >> v; X = (X + v) % N; } } return 0; }