12814번 - Hyperways 다국어

The intergalactic company Oods&co is going to build a network of hyperways that will connect the planets of our galaxy. They have already prepared a construction plan, i.e., a sequential order of building the hyperways. Each hyperway will be a bidirectional corridor that will connect two (not necessarily distinct) planets.

A hyperway is safe if it is not the only hyperway that connects (directly or indirectly) some pair of planets. In other words, a hyperway H is unsafe if there are two planets A and B such that when traveling from A to B we have to use H. (Alternately, note that safe hyperways are the ones that lie on some cycle.)

You will be given the order in which hyperways will be constructed. After each construction there may be some hyperways which have just become safe. (Including, possibly but not necessarily, the hyperway that was just built.) Count those hyperways.

Note that if a hyperway is already safe, it will remain safe for the rest of the construction.

On the first line of input are two integers n and m: n is the number of planets in the plan, m is the number of hyperways. The planets are numbered 1 . . . n.

Each of next m lines consists of two space separated integers – the ids of planets next hyperway will join. There can be a hyperway connecting a planet with itself. There can be a multiple hyperways between two planets.

In all test cases, n ≤ 10⁶ and m ≤ 2 · 10⁶.

For each hyperway in the input, output a single line with a single integer: the number of hyperways that just became safe.