F. Mooclear Reactor 3
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie is trying to develop energy-efficient moolecules for her mooclear reactor!

She has $$$n$$$ individual atoms, numbered from $$$1$$$ to $$$n$$$. Initially, each atom forms its own single-atom moolecule.

There are $$$m$$$ reactive pairs of atoms. If a reactive pair of atoms ever ends up in the same moolecule, the moolecule becomes unstable and immediately explodes. After the explosion, all atoms in the moolecule separate into single-atom moolecules.

Bessie performs $$$q$$$ experiments in her lab. In the $$$i$$$-th experiment, she attempts to merge the moolecule containing atom $$$u_i$$$ with the moolecule containing atom $$$v_i$$$:

  1. If atom $$$u_i$$$ and atom $$$v_i$$$ are in different moolecules, Bessie combines the moolecules into one moolecule containing the atoms from both.
  2. If the newly combined moolecule contains at least one reactive pair of atoms, it instantly explodes into single-atom moolecules.

After each experiment, Bessie wants to know the number of moolecules in her laboratory. Help her compute this count after every experiment!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$2 \le n \le 2\cdot 10^5$$$, $$$0 \le m \le 2\cdot 10^5$$$, $$$1 \le q \le 2\cdot 10^5$$$) — the number of atoms, the number of reactive pairs, and the number of experiments, respectively.

Each of the next $$$m$$$ lines contains two integers $$$x_j$$$ and $$$y_j$$$ ($$$1 \le x_j, y_j \le n$$$, $$$x_j \neq y_j$$$), denoting that atoms $$$x_j$$$ and $$$y_j$$$ are a reactive pair. It is guaranteed that $$$(x_i,y_i)\ne (x_j,y_j)$$$ and $$$(x_i,y_i)\ne (y_j,x_j)$$$ for all $$$1\le i \lt j\le m$$$.

Each of the next $$$q$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), denoting the atoms Bessie attempts to merge in the $$$i$$$-th experiment.

It is guaranteed that the sums of $$$n$$$, $$$m$$$, and $$$q$$$ over all test cases do not exceed $$$2\cdot 10^5$$$.

Output

For each test case, print $$$q$$$ integers, each on a new line. The $$$i$$$-th integer should be the total number of moolecules after the $$$i$$$-th experiment.

Example
Input
2
5 2 5
1 3
2 4
1 2
3 4
1 4
1 3
2 5
4 0 4
1 2
3 4
2 4
1 2
Output
4
3
5
5
4
3
2
1
1
Note

In the first test case, there are two reactive pairs: $$$(1,3)$$$ and $$$(2,4)$$$.

In the first two experiments, Bessie successfully merges two moolecules, and the number of moolecules decreases by one each time.

The third and fourth experiments both cause explosions, causing the number of moolecules to return to $$$5$$$.

The fifth experiment is a successful merge, so the number of moolecules decreases to $$$4$$$.