Scientists have recently discovered a high-molecular organic compound called SHTSC. The molecules of this substance are composed of multiple atoms connected by chemical bonds. SHTSC is highly unstable, and the chemical bonds between its atoms frequently break or reform, accompanied by cool sound effects and light shows.

However, to the scientists' amazement, SHTSC maintains a special property throughout its changes: there is no sequence of atoms $a_1, a_2, \dots, a_n$ ($n \ge 3$) such that $a_1$ is connected to $a_2$, $a_2$ to $a_3$, $\dots$, $a_{n-1}$ to $a_n$, and $a_n$ to $a_1$ via chemical bonds, while no other chemical bonds exist between these atoms. Scientists have labeled the atoms of SHTSC from $1$ to $n$ and have provided you with the initial state of SHTSC and the changes in the chemical bonds. They want to know how many molecules SHTSC has split into at certain moments during the experiment.

Input

The first line contains two integers: $n, m$, representing the total number of atoms and the initial number of chemical bonds in SHTSC.

The next $m$ lines each contain two integers $a, b$ ($1 \le a, b \le n$), representing that atoms $a$ and $b$ are connected by a chemical bond in the initial state. It is guaranteed that each pair $(a, b)$ appears at most once.

The $(m+2)$-th line contains an integer $q$, representing the total number of operations.

Each of the following $q$ lines contains one of the following three operations:

1. A i j: A new chemical bond is formed between atom $i$ and atom $j$.
2. D i j: The existing chemical bond between atom $i$ and atom $j$ is broken.
3. Q: Query the current number of distinct molecules SHTSC has split into.

It is guaranteed that all experimental operations are valid.

Output

For each Q operation, output a single integer on a new line representing the number of molecules at that moment.

Examples

Input 1

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

Output 1

1
2
3
2
1

Constraints

For 30% of the data, $n, q \le 1000$.

For 100% of the data, $n \le 5000$, $m \le 200000$, $q \le 10000$.