Background

SHOI2014 day2t1

Problem Description

Scientists have recently discovered a polymer organic compound called SHTSC. The molecules of this substance consist of one or more atoms, and atoms are connected to each other by chemical bonds. SHTSC is very unstable: the chemical bonds between its atoms often break or reconnect, accompanied by cool sound effects and visual effects.

However, what greatly surprised the scientists is that during these changes, SHTSC always maintains a special property: there does not exist an atom sequence $a_1,a_2,\ldots,a_n \ (n>3)$ such that $a_1$ is bonded to $a_2$, $a_2$ is bonded to $a_3$, $\ldots$, $a_{n-1}$ is bonded to $a_n$, and $a_n$ is bonded to $a_1$, but there are no other chemical bonds among them.

Now the scientists label the atoms of SHTSC from $1$ to $n$, and tell you the initial form of SHTSC and the changes of chemical bonds between atoms. They want to know, at certain moments during the experiment, into how many molecules SHTSC is split.

Input Format

The first line contains two integers $n, m$, representing the total number of atoms in SHTSC and the number of initial chemical bonds.
Starting from the second line, the next $m$ lines each contain two integers $a, b \ (1 \leq a,b \leq n)$, indicating that atoms $a$ and $b$ are connected by a chemical bond in the initial state. The data guarantees that each pair $a, b$ appears only once.
Line $m+2$ contains an integer $q$, representing the total number of operations in the experiment.
The following $q$ lines each describe one of the three types of operations below:

1. A i j means a new chemical bond is formed between atom $i$ and atom $j$.
2. D i j means the existing chemical bond between atom $i$ and atom $j$ is broken.
3. Q asks how many different molecules SHTSC is currently split into.
   The data guarantees that all operations are valid.

Output Format

For each Q operation, output one line with one integer, the number of molecules at that moment.

7 10
1 2
2 3
3 4
4 1
1 3
2 4
5 6
6 7
7 5
2 5
10
Q
D 2 5
Q
D 5 6
D 5 7
Q
A 2 5
Q
A 5 6
Q

1
2
3
2
1

Hint

For $30\%$ of the testdata, $n, q \leq 1000$.

For $100\%$ of the testdata, $n \leq 5000, m \leq 200000, q \leq 10000$.

Translated by ChatGPT 5