409610: GYM103643 M Thomas Game Revisited

Thomas has been caught game (again)! Instead of playing on a 2d grid, he is now playing on a multidimensional space that has no regard to fundamental axioms of geometry, more commonly known as a graph. Thomas is on a graph of $$$n$$$ nodes completely full with an undirected edge between all $$$u$$$ and $$$v$$$ such that $$$(1 \leq u < v \leq n)$$$. Teacher is trying to catch Thomas and has already blocked off $$$m$$$ of these edges.

Thomas is trying to run out of the graph before Teacher comes and catches him. Thomas is able to escape from a node if it has degree at most $$$1$$$ or there is at most $$$1$$$ edge out of it.

As it turns out, Teacher still has not used his secret weapon yet. Teacher has a powerful device that is able to delete $$$2$$$ nodes. When a node is deleted, all of the edges that go out of that node are removed from the graph.

Thomas now wants your help to help check if escaping from Teacher's grasp is possible. Thomas will ask you $$$q$$$ queries, where each query is two integers $$$a$$$ $$$b$$$. Thomas wants you to answer the total number of escapable nodes in the graph if Teacher deletes the nodes $$$a$$$ and $$$b$$$ with his machine.

The first line containers three integers $$$n$$$ $$$m$$$ $$$k$$$ $$$(2 \leq n \leq 2 \cdot 10^5), (1 \leq q \leq 2 \cdot 10^5), (0 \leq m \leq \min(\frac{n(n-1)}{2}, 2 \cdot 10^5))$$$. The next $$$m$$$ lines contain two integers each $$$u$$$ $$$v$$$ $$$(1 \leq u, v \leq n, u \neq v)$$$. It is guaranteed no edge will appear twice in the input. The following $$$q$$$ lines contain two integers each $$$a$$$ $$$b$$$ $$$(1 \leq a, b \leq n, a \neq b)$$$ denoting a query of Teacher deleting the nodes $$$a$$$ and $$$b$$$. All queries are independant, meaning Teacher does not actually delete any nodes, but rather we are considering the case if he hypothetically did.

You will output $$$q$$$ lines, the $$$i$$$'th line denoting the answer to the $$$i'th$$$ query.

5 3 2
1 2
2 4
4 5
1 2
4 1

2
0

In the first query, the escapable nodes are $$$4$$$ and $$$5$$$.

In the second query, there are no escapable nodes.

$$$---------------------------------------------$$$

Problem idea: 3366

Problem preparation: 3366

Occurrences: Intermediate 7, Advanced 7