Statement

Recent studies have shown that there is indeed intelligent life on Mars. The problem is that now humanity is at war with the Martians! Our best bet for survival is 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 before the bombing, 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.