Joitter에서 친구 사귀기는 재미있다

Joitter는 친구와 추억을 공유할 수 있는 인기 소셜 미디어이다.

Joitter에서는 다른 사용자를 팔로우할 수 있다. 예를 들어 사용자 a가 사용자 b를 팔로우하면, a는 타임라인에서 b의 게시글을 읽을 수 있다. 이때 b가 a를 맞팔로우할지는 정해져 있지 않다. 다만 사용자가 자기 자신을 팔로우하는 것과, 같은 사용자 b를 두 번 팔로우하는 것은 불가능하다.

사용자 1, 사용자 2, ..., 사용자 N, 이렇게 N명의 사용자가 Joitter를 쓰기 시작했다. 처음에는 아무도 다른 사용자를 팔로우하지 않는다. 이후 M일 동안 팔로우 이벤트가 일어난다. i일째에 사용자 A_i가 사용자 B_i를 팔로우한다.

Joitter 운영진은 M일 중 한 번 소셜 교환 이벤트를 열 계획이다. 소셜 교환 이벤트는 다음과 같이 진행된다.

1. 사용자 한 명을 고른다. 이 사용자를 x라 한다.
2. x가 지금 팔로우하고 있는 사용자 한 명을 고른다. 이 사용자를 y라 한다.
3. 사용자 z를 고른다. z는 x와 다르고, x가 팔로우하지 않는 사용자이며, y가 팔로우하는 사용자이고, z가 y를 팔로우하는 사용자이다.
4. x가 z를 팔로우한다.
5. (x, y, z) 세 명을 더 이상 고를 수 없을 때까지 이 과정을 반복한다.

운영진은 이벤트를 언제 열지 아직 정하지 않았다. 각 i ($1 \le i \le M$)에 대해, i일째 팔로우 이벤트 直後에 이벤트가 열린다고 가정할 때 이벤트 이후 각 사용자가 팔로우하는 사용자 수의 총합이 가질 수 있는 최댓값을 알고 싶어 한다. 소셜 교환 이벤트는 다음 날 팔로우 이벤트 전에 끝난다.

각 i에 대해 이 최댓값을 계산하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다. 입력의 모든 값은 정수이다.

N M
A1 B1
.
.
.
AM BM

표준 출력에 M개의 줄을 출력한다. i번째 줄에는 i일째 팔로우 이벤트 직후에 소셜 교환 이벤트가 열릴 때, 이벤트 이후 각 사용자가 팔로우하는 사용자 수의 총합의 최댓값을 출력한다.

• $2 \le N \le 100000$
• $1 \le M \le 300000$
• $1 \le A_i \le N$ ($1 \le i \le M$)
• $1 \le B_i \le N$ ($1 \le i \le M$)
• $(A_i, B_i) \ne (A_j, B_j)$ ($1 \le i < j \le M$)
• 시간 제한 2000 ms, 메모리 제한 512 MB