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$.

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.

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 $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$.

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

* 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$

* The scores from the contest might be different than the scores you get here

h2. Exemplu

h2. Exemple

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

|
5 4 2

| 5 4 2

5 1
3 2
2 5

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$).

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") ==