Cacti Classification

This is not about reconstructing the cactus. That would be a trap and also a great way to get cooked by the query limit. We only need cycle membership and cycle length up to $14$, so we classify edges by their position inside their own cycle by label order.

Core cactus fact

In any connected graph, an edge is not a bridge iff it belongs to some cycle. In a cactus, such a cycle is unique.

Now the important cactus-specific fact:

If two distinct edges from the same simple cycle of a cactus are deleted, the graph becomes disconnected.

Why? A cycle gives exactly one alternate route after deleting one of its edges. Delete a second edge from that same cycle, and that alternate route is broken too. There cannot be some sneaky outside path reconnecting the broken parts, because then one of those cycle edges would belong to another simple cycle, violating the cactus condition. Cactus graphs are prickly but honest.

So:

• remove a bridge: disconnected;
• remove one edge from a cycle: still connected;
• remove two edges from the same cycle: disconnected.

That is basically the full problem.

Brackets

Process edge labels from $1$ to $m$.

For a non-bridge edge $e$, define its bracket as the number of earlier-labeled edges on its unique cycle. If this number is $0,1,\dots,14$, we put it in that bracket. Bridges and cycle edges with at least $15$ earlier cycle edges go to bracket $15$.

For every $i=0,1,\dots,14$, maintain a connected edge set $G_i$:

$$G_i = E \setminus \{\text{edges already placed in bracket } i\}.$$

Why is $G_i$ always connected? Because bracket $i$ contains at most one edge from any cycle: on a cycle, the first edge has bracket $0$, the second has bracket $1$, and so on. It contains no bridges. Deleting at most one edge from each cycle and no bridges keeps the cactus connected.

Implementation-wise, we store each $G_i$ by the query number that created it. Query number $0$ means the full edge set $E$.

Pass 1: find every bracket

Suppose we are processing edge $e$.

For each $i\in[0,14]$, ask:

$$P(i) = [G_i\setminus\{e\}\text{ is connected}].$$

Consider cases.

If $e$ is a bridge, removing it disconnects every connected $G_i$, so $P(i)=0$ for all $i$.

Otherwise, let $b$ be the number of earlier edges on $e$'s cycle.

• If $i<b$, then bracket $i$ already contains an earlier edge from this same cycle. So $G_i$ is already missing one cycle edge, and deleting $e$ removes a second one. Disconnected.
• If $i\ge b$, then bracket $i$ contains no earlier edge from this cycle. Later edges have not been processed yet. Deleting $e$ removes only one edge from the cycle. Connected.

So $P(i)$ is monotone:

$$0,0,0,\dots,0,1,1,\dots,1.$$

Binary search the first true value in $[0,14]$. This takes at most $4$ queries because $15<16$. If no true value exists, put $e$ into bracket $15$. Otherwise, suppose the first true is $b$; then the query $G_b\setminus\{e\}$ is connected, and it becomes the new stored version of $G_b$.

Pass 1 costs at most $4m$ queries.

Pass 2: recover bridge / length / big

Now all brackets are finalized.

If an edge is in bracket $14$ or $15$, ask once whether $E\setminus\{e\}$ is connected.

• If not connected, $e$ is a bridge, output $-1$.
• If connected, $e$ is on a cycle of length at least $15$, output $0$ for big cycle.

Why length at least $15$? Bracket $14$ means this is the $15$-th edge of its cycle. Bracket $15$ and non-bridge means even later.

Now take an edge $e$ in bracket $b\le 13$. Let its cycle length be $L$.

For each $i\in[0,14]$, we want to know whether $G_i\setminus\{e\}$ is bad/disconnected. There is one annoying detail: when $i=b$, the graph $G_b$ already has $e$ removed, so asking to remove $e$ again is invalid. We simply treat $i=b$ as bad without querying.

For $i\ne b$:

• If $i<L$, bracket $i$ contains another edge of this same cycle, so deleting $e$ removes two cycle edges. Bad.
• If $i\ge L$, bracket $i$ contains no edge of this cycle, so deleting $e$ removes only $e$. Good.

Therefore:

$$\text{Bad}(i)=1 \quad\text{exactly for}\quad i<\min(L,15).$$

So Bad is also monotone: true prefix, false suffix. Binary search the first non-bad index $K$.

• If $K\le 14$, then $L=K$.
• If $K=15$, then $L\ge 15$, so output $0$.

This pass also uses at most $4m$ queries.

Query bound

Pass 1: at most $4m$ queries.

Pass 2: at most $4m$ queries.

Total: at most $8m$, exactly within the limit. No cactus reconstruction, no vertex names, no drama.