Hyperways

The intergalactic company Oods&co is building a network of hyperways that connects the planets of our galaxy. The construction plan is already prepared, and it fixes the order in which the hyperways are built. Each hyperway is a bidirectional corridor between two planets, and both ends may be the same planet.

A hyperway $H$ is unsafe if there are two planets $A$ and $B$ such that every trip from $A$ to $B$ has to use $H$. If no such pair of planets exists, $H$ is safe, which is the same as saying that $H$ is not the only hyperway connecting some pair of planets, directly or indirectly. Safe hyperways are exactly the ones that lie on some cycle.

You are given the order in which the hyperways are built. Right after a hyperway is built, some hyperways may have just become safe, and the hyperway that was just built may be one of them. Count them after every construction. A hyperway that is already safe stays safe for the rest of the construction.

The first line contains two integers $n$ and $m$. Here $n$ is the number of planets in the plan and $m$ is the number of hyperways. The planets are numbered $1$ through $n$.

Each of the next $m$ lines contains two space separated integers, the ids of the planets that the next hyperway joins. A hyperway may connect a planet with itself, and several hyperways may connect the same two planets.

In all inputs, $1 \le n \le 10^6$ and $1 \le m \le 2 \times 10^6$.

For each hyperway in the input, print one line with one integer, the number of hyperways that became safe right after that hyperway was built.