도로는 사치품이 아니라 이동 수단이다

나라 N에는 $n$개의 도시가 있으며, 1번부터 $n$번까지 번호가 붙어 있습니다. 그런데 이 나라에는 도로가 하나도 없습니다! 대통령은 $m$일 동안 매일 도로를 한 개씩, 총 $m$개의 도로를 건설하기로 결정했습니다. 인구 이동을 돕기 위해 모든 도로는 일방통행으로 만들고, 도시 $i$에서 도시 $j$로 가는 경로가 있으면 도시 $j$에서 도시 $i$로 가는 경로는 없도록 도로망을 계획합니다.

새 도로를 널리 알리기 위해 나라 N은 매일 도시들을 돌며 자동차 시범 운행을 진행합니다. 각 자동차는 한 도시에서 출발해 그날까지 건설된 도로를 따라 달린 뒤, 어느 도시에서든 운행을 마칩니다. 출발 도시와 도착 도시가 같아도 됩니다. 이 경우 자동차는 도로를 한 번도 지나지 않습니다. 주민들을 즐겁게 하고 운전자의 연료를 아끼기 위해, 조직위원회는 매일 다음 규칙에 따라 운행 경로를 고르기로 했습니다.

1. 모든 도시를 어떤 자동차가 반드시 방문해야 합니다. 방문한 도시는 자동차 경로의 출발 도시, 도착 도시, 그리고 경로 중간에 지나는 모든 도시입니다.
2. 어떤 도시도 자동차들이 두 번 이상 방문해서는 안 됩니다.
3. 사용하는 자동차의 총 대수가 최소여야 합니다.

나라 N의 교통부는 앞으로 $m$일 동안 날마다 도로를 정확히 하나씩 건설하기로 이미 계획했습니다. 교통부는 매일 필요한 자동차의 최소 대수를 알고 싶어 합니다. $i$일에는 1일부터 $i$일까지 건설된 도로를 모두 사용할 수 있다고 봅니다.

첫 줄에 두 정수 $n$과 $m$이 주어집니다($2 \leq n \leq 1000$, $1 \leq m \leq 100\,000$). 각각 도시의 수와 도로를 건설하는 날의 수입니다. 이어지는 $m$개의 줄에는 각각 두 정수 $u_i$와 $v_i$가 주어집니다($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$). 이는 $i$일에 도시 $u_i$에서 도시 $v_i$로 가는 일방통행 도로가 건설된다는 뜻입니다. 이미 도로로 연결된 두 도시 사이에 도로를 또 건설할 수도 있습니다. 어떤 도로를 건설한 뒤에도, 도시 $a$에서 도시 $b$로 가는 경로가 있으면 도시 $b$에서 도시 $a$로 가는 경로는 없다는 것이 보장됩니다.

$m$개의 정수를 출력합니다. $i$번째 정수는 처음 $i$개의 도로를 건설한 뒤 필요한 자동차의 최소 대수입니다.

첫 번째 예제에서는 처음 두 도로를 건설한 뒤에도 자동차가 최소 2대 필요합니다. 예를 들어 한 대는 도시 1에서 도시 2로 이동하고, 다른 한 대는 도시 3에서 출발해 도시 3에서 운행을 마칠 수 있습니다. 모든 도로를 건설한 뒤에는 $1 \rightarrow 2 \rightarrow 3$ 경로를 도는 자동차 한 대면 충분합니다.

두 번째 예제에서는 모든 도로를 건설한 뒤 자동차 두 대로 모든 도시를 방문할 수 있습니다. 하지만 어떤 도시도 두 번 이상 방문해서는 안 된다는 조건 때문에 이 방법은 쓸 수 없습니다.