| Codeforces Round 1135 (Div. 2) |
|---|
| Finished |
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$$$:
After each experiment, Bessie wants to know the number of moolecules in her laboratory. Help her compute this count after every experiment!
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$$$.
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.
25 2 51 32 41 23 41 41 32 54 0 41 23 42 41 2
435543211
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$$$.
| Name |
|---|


