== include(page="template/taskheader" task_id="martian-war") ==

Poveste şi cerinţă...

Recent studies have shown that there is indeed intelligent life on Mars. The problem is that now humanity is at war with the Martians and our best bet for survival is that we need to strike first. On Mars there is a complex railroad system of $n$ cities connected by $m$ bidirectional railroads.
 
Earth has called upon the best bomber there is, mister RANDy, to strike down those railroads. Because he is a maniac, he only has one bomb left so he can only strike down a single one of those railroads. RANDy will only target strategic railroads. A railroad is strategic if and only if there exists a pair of cities ($x, y$) such that you can reach $x$ from $y$ and after bombing the given railroad, you can no longer reach $x$ from $y$.
 
The Martians are starting to pick up on our plan, so they are now constructing $q$ additional railroads. After the construction of each new railroad, RANDy wants to know how many strategic railroads there are. RANDy now asks you to help him find the answer he seeks.

h2. Date de intrare

Fişierul de intrare $martian-war.in$ ...

Input file $martian-war.in$ will contain on the first line $n$, the number of cities on the Martian surface, $m$, the number of railroads connecting those cities and q, the number of additional railroads that the Martians will be constructing.
 
On the next $m$ lines you will find a pair ($x, y$), meaning that there is a bidirectional railroad from city $x$ to city $y$.
 
On the next $q$ lines you will find a pair ($x, y$), meaning that the Martians will construct a railroad from city $x$ to city $y$.

h2. Date de ieşire

În fişierul de ieşire $martian-war.out$ ...

The output file $martian-war.out$ will contain $q$ lines, the $ith$ line will contain a single number $s$, representing the number of strategic railroads after the Martians have constructed the first $i$ new railroads

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ n, m, q ≤ 2.5 * 10^5$
* The graph is not guaranteed to be connected
* For tests worth $30$ points, $1 ≤ n, m, q ≤ 10^3$
* For tests worth $40$ more points, $1 ≤ n, m, q ≤ 10^5$

h2. Exemplu
table(example). |_. martian-war.in |_. martian-war.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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

|

table(example). |_. martian-war.in |_. martian-war.out |
| 6 5 2
5 1
3 2
2 5
4 2
1 2
4 3
6 5
| 0
1
|
 

h3. Explicaţie

...

For the first sample, after the first built railroad, the strategic railroads are ($2, 4$) and ($2, 3$). After the second built railroad, the only strategic railroad is ($2, 4$).

== include(page="template/taskfooter" task_id="martian-war") ==