409494: GYM103584 G Perfect Cacti: Part 1

Cacti are basically desert trees, and they deserve some love too.

After staring at a bunch of cacti, you've realized that, indeed, cacti are quite beautiful! In fact, as you looked at them more, you realize that some "perfect cacti" look geometric:

Not only are cacti geometric, but they're also recursive (like trees)! However, so far you've only been able to cultivate perfect $$$k$$$-cacti of height 1 – that is, cacti that resemble perfect polygons with $$$k$$$ sides.

Suddenly, you remember something from class: just like trees, cacti can be graphs too! In fact, we can treat the perfect cactus graph as an unweighted, undirected graph between vertices (of the polygon). You begin to wonder: given a perfect cacti graph, how long does it take to get from one node to another? Or, even better – can you find these values, even as edges are broken and restored?

The first line begins with three integers, $$$k$$$ $$$(3 \leq k \leq 10^{18})$$$, $$$h$$$ $$$(h=1)$$$ and $$$q$$$ $$$(1 \leq q \leq 10^5)$$$. $$$k$$$ and $$$h$$$ describe the cactus graph (which is a $$$k$$$-cactus of height $$$h$$$).

It is guaranteed that the number of nodes in the perfect cactus graph does not exceed $$$10^{18}$$$.

Then, $$$q$$$ lines follow, each containing three integers: $$$a, i, j$$$. The type of query is determined by $$$a$$$:

• $$$a=1$$$: Find the minimum number of edges needed to get from vertex $$$i$$$ to vertex $$$j$$$.
• $$$a=2$$$: Remove the edge from vertex $$$i$$$ to vertex $$$j$$$. It is guaranteed that this edge exists in the perfect cactus graph.
• $$$a=3$$$: Restore the edge from vertex $$$i$$$ to vertex $$$j$$$. It is guaranteed that this edge used to exist in the perfect cactus graph, but is currently not in the graph.

Since the graph is not directly given to you, the vertices are labelled $$$0 \ldots k-1$$$, starting at the root, and going clockwise.

For each query where $$$a=1$$$, print out the minimum number of edges needed to get from vertex $$$i$$$ to vertex $$$j$$$. If no path exists, output -1.

10 1 7
1 0 8
2 0 9
1 0 8
2 0 1
1 0 8
3 0 9
1 0 8

2
8
-1
2