Making Friends on Joitter is Fun

Joitter is a trending social media service where you can share your memories with your friends.

In Joitter, you can follow other users. For example, when user a follows user b, user a can read user b's posts on the timeline. In this case, user b may or may not follow user a back. However, a user cannot follow themselves, and a user cannot follow the same user b more than once.

N users, user 1, user 2, ..., user N, have started using Joitter. At first, none of them follows any other user. From now on, for M days, following events occur: on the i-th day, user A_i follows user B_i.

The Joitter staff plans to hold a social exchange event on the service once during the M days. A social exchange event works as follows:

1. Select one user. Call this user x.
2. Select one user that x currently follows. Call this user y.
3. Select one user z such that z is different from x, x does not follow z, y follows z, and z follows y.
4. x follows z.
5. Repeat these steps until no tuple (x, y, z) can be selected.

The staff has not decided when to hold the event. For each i ($1 \le i \le M$), they want to know the maximum possible total number of users that each user follows after the social exchange event, assuming the event happens right after the following event of day i. The social exchange event finishes before the following event of the next day.

Write a program that calculates this maximum for each i.

Read the following data from the standard input. All values are integers.

N M
A1 B1
.
.
.
AM BM

Write M lines to the standard output. On the i-th line, output the maximum total number of users each user follows after the social exchange event, if the event happens right after the following event of day 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$)
• Time limit: 2000 ms. Memory limit: 512 MB.