Make it a rule - always fly GraphAero!
Air travel is now within everyone's reach! However, due to intense competition in the passenger transport industry, only two airlines remain: "GraphAero Airlines" and "Aerofloat".
"GraphAero Airlines" is in a phase of rapid expansion. To maximize profits—or rather, to enhance passenger convenience—the company introduces one new flight every month. Meanwhile, "Aerofloat" must adapt by adding flights that replicate the busiest routes of "GraphAero Airlines". A flight is deemed the busiest if there exists a pair of cities such that one can travel (possibly with layovers) from one city to another using the airline's flights, but if this particular flight is removed, reaching the destination becomes impossible. Analysts at "Aerofloat" need to continuously assess the situation to determine how many busiest flights exist at any given time.
Since you've always wanted to fly at a discounted rate (a discount of 10^(-5)%), you've decided to assist. Keep in mind: planes fly globally! There can be multiple flights between two major cities, and cities can be so vast that flights operate within a single city. Flights are available in both directions.
Input
The first line contains two integers n (1 ≤ n ≤ 10^5) and m (0 ≤ m ≤ 10^5) — the initial number of flights operated by "GraphAero Airlines". The next m lines provide details of each flight, specifying the numbers of the two cities connected by the flight. The subsequent line contains the integer k (1 ≤ k ≤ 10^5) — the number of flights to be added. The descriptions of these additional flights follow in the same format.
Output
After each new flight is added, output a single number on a separate line — the count of the busiest flights.