하이퍼웨이

은하 기업 Oods&co가 우리 은하의 행성을 잇는 하이퍼웨이 망을 건설한다. 건설 계획은 이미 준비되어 있고, 하이퍼웨이를 놓는 순서가 그 계획에 들어 있다. 하이퍼웨이 하나는 두 행성을 잇는 양방향 통로이며, 두 끝이 같은 행성일 수도 있다.

하이퍼웨이 $H$가 안전하지 않다는 것은, $A$에서 $B$로 가려면 반드시 $H$를 지나야 하는 두 행성 $A$, $B$가 있다는 뜻이다. 그런 행성 쌍이 없으면 $H$는 안전하다. 즉 (직접 또는 간접으로) 어떤 행성 쌍을 잇는 유일한 하이퍼웨이가 아니면 안전하다. 안전한 하이퍼웨이는 어떤 사이클 위에 놓인 하이퍼웨이와 정확히 같다.

하이퍼웨이를 놓는 순서가 주어진다. 하이퍼웨이를 하나 놓을 때마다 그 직후에 새로 안전해진 하이퍼웨이가 있을 수 있고, 방금 놓은 하이퍼웨이 자신도 거기에 포함될 수 있다. 건설마다 새로 안전해진 하이퍼웨이의 개수를 세라. 한 번 안전해진 하이퍼웨이는 공사가 끝날 때까지 계속 안전하다.

첫째 줄에 두 정수 $n$과 $m$이 주어진다. $n$은 계획에 들어 있는 행성의 수, $m$은 하이퍼웨이의 수다. 행성의 번호는 $1$부터 $n$까지다.

다음 $m$개의 줄에는 각각 공백으로 구분된 두 정수가 주어진다. 다음으로 놓을 하이퍼웨이가 잇는 두 행성의 번호다. 한 행성을 자기 자신과 잇는 하이퍼웨이도 있을 수 있고, 같은 두 행성을 잇는 하이퍼웨이가 여러 개 있을 수도 있다.

모든 입력에서 $1 \le n \le 10^6$, $1 \le m \le 2 \times 10^6$이다.

입력에 주어진 각 하이퍼웨이에 대해, 그 하이퍼웨이를 놓은 직후 새로 안전해진 하이퍼웨이의 개수를 한 줄에 하나씩 출력한다.