I am currently solving IOI problems to get ready for the upcoming IOI problem and this one is really cool in my opinion. I'll explain the way I constructed my solution, it may not be optimal or easiest but it worked and it is pretty fast and easy to code in my opinion.

First let's see how do we keep track of cycle formation, i.e. how to know if a cycle has formed after the addition of some edge. This is pretty easy to do if we use Union Find. If the edge connects vertices that are already from the same set, obviously we get a cycle. Cycle tracking will be the only thing we need in order to solve the problem.

Let's number the states we could be in (according to my solution) :

State 1 — linear graph (set of disjoint paths) — answer is the number of vertices in the graph.

State 2 — there is a single cycle — answer is the number of vertices that lie on the cycle

State 3 — there is some vertex of degree 3 or larger — the critical vertices can be only it or its neighbours

State 4 — "blocked" graph, i.e. there are no critical vertices — answer is 0

Now, suppose a query of connecting vertices A and B comes. Let's see what we do in each possible case.

If we are in state 1 currently : if the vertices are from different sets — we continue being in state 1. If the vertices are from the same set, simply use a dfs to find the amount of vertices that lie on the cycle, and change the state to 2.

If we are in state 2 currently : if after adding the edge, the degrees of A and B are both less than 3 and a new cycle is formed — go to state 4 as the graph will be forever blocked. If the degrees of A and B are both less than 3 and no new cycle is formed — simply stay in the same state. If A or B's degrees becomes 3 go to state 3.

In my solution, upon going to state 3 we create 4 separate graphs. Since upon going in state 3 we have at most 4 candidates (the vertex with degrees 3 and its neighbours) we create 4 different graphs in each of which some candidate doesn't exist. Now what we do is keep track of cycle formation in those 4 new graphs. If at some point some graph becomes non-linear — simply the candidate it corresponded to is no longer critical and we can throw that graph away.

If we are in state 3 currently : update in all 4 graphs adding the edge (unless it connects to the removed vertex, the candidate) and check if a cycle is formed. If in some graph a cycle is formed, declare the graph as blocked and the candidate it corresponded to as non-critical. At the end the answer for your query will be the number of graphs that are still linear (0~4).

If we are in state 4 — simply do nothing, and return 0 upon queries, once blocked the graph can't be unblocked.

Note that my solution relies on the observation that once a vertex becomes non-critical, it can never be critical again. The idea of keeping 4 graphs at once seemed simplest to me, there may be another easier solution but I do not think that implementing that solution is hard at all.

Assuming Union-Find's complexity is O(log* N) we get worst-case O(4 * Q * log* N) = O(Q * log* N)

If you have any questions, feel free to ask me :)

IGNORED

Ah, the nostalgia. I tried something that involved a loooot of casework, and almost got the problem working for full score — I was failing just on 1 or 2 test cases per batch (which means it was probably the same 1 or 2, and I missed a special case). It's kind of funny to watch how many people had a hard time optimizing already working solutions, while it was a "0 or 100" problem for me...