Roads are not a luxury but a way to travel

Country N has $n$ cities, numbered from 1 to $n$, but it has no roads at all. The president has decided to build $m$ roads over $m$ days, one new road per day. To encourage migration, every road is one-way, and the road network is planned so that if there is a path from city $i$ to city $j$, there is no path from city $j$ to city $i$.

To promote the new roads, country N holds a series of test drives through its cities every day. Each car starts in some city, drives along the roads built so far, and ends in some city. A car may start and end in the same city, in which case it drives no roads. To please residents and save drivers' fuel, the organizers choose the set of routes each day under these rules:

1. Every city must be visited by a car. A city counts as visited if it is the start, the end, or an intermediate city of any car's route.
2. No city may be visited more than once by the cars.
3. The total number of cars used must be minimal.

The transport ministry of country N has already scheduled the construction of exactly one road for each of the next $m$ days. For each day, the ministry asks you to find the minimum number of cars needed for the test drives. On day $i$, all roads built on days $1, 2, \ldots, i$ are available.

The first line contains two integers $n$ and $m$ ($2 \leq n \leq 1000$, $1 \leq m \leq 100\,000$), the number of cities and the number of days. Each of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$), meaning that on day $i$ a one-way road from city $u_i$ to city $v_i$ is built. A road may be built between two cities that are already connected by a road. It is guaranteed that after each road is built, if there is a path from city $a$ to city $b$, then there is no path from city $b$ to city $a$.

Print $m$ numbers. The $i$-th number is the minimum number of cars needed after the first $i$ roads are built.

In the first example, even after the first two roads are built, at least two cars are still needed. For instance, one car can drive from city 1 to city 2, and another car can start and finish in city 3. After all roads are built, one car is enough: it drives along $1 \rightarrow 2 \rightarrow 3$.

In the second example, after all roads are built, two cars could visit all cities, but the rule that no city may be visited more than once rules this out.