| Fişierul intrare/ieşire: | martian-war.in, martian-war.out | Sursă | IIOT 2021-22 Runda 1 |
| Autor | Bogdan Ioan Popa | Adăugată de |  Stefan Dascalescu •stefdascalescu |
| Timp execuţie pe test | 1 sec | Limită de memorie | 32768 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Martian War
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.
Date de intrare
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.
Date de ieşire
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
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
- The scores from the contest might be different than the scores you get here
Exemple
| martian-war.in | martian-war.out |
|---|---|
| 5 4 2 5 1 3 2 2 5 4 2 1 2 5 3 | 2 1 |
| 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 |
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).
