Joitter is a trending social media where you can share your memories with your friends. In Joitter, you can follow other users. For example, when a user follows another user , user can read user 's posts on the timeline. In this case, it is possible that user follows back user or not. However, it is impossible that user follows him/herself or user follows a particular user more than once. users, consisting of user , user , …, user , have started using Joitter. At first, none of them follows any other users.
From now on, for days, following events occur: user follows user on the -th day . The official of Joitter is planning to hold a social exchange event on its service once during the days. A social exchange event occurs as follows:
- Select one user. We will call the selected user .
- Select one user being followed by at the moment. We will call the selected user .
- Select one user such that: is different from , is not following , is following , and is following .
- follows .
- Reiterate these processes until it is impossible to select a tuple .
The official of Joitter still has not decided when to hold the social exchange event. So, they would like to know the maximum value of the total sum of the number of users each user follows after the social exchange event, if it happens right after the following event of the -th day, for each . We assume that the social exchange event finishes before the following event on the next day.
Write a program that, given the number of users and following events during days, calculates the maximum value of the total sum of the number of users each user follows after the social exchange event, if the social exchange event falls right after the following event of the -th day, for each .
Input Specification
Output Specification
Write lines to the standard output. In the -th line , output the maximum value of the total sum of the number of users each user follows after the social exchange event, if the social exchange event falls right after the following event of day .
Constraints
.
.
.
.
.
.
Subtasks
- (1 point) .
- (16 points) .
- (83 points) No additional constraints.
Sample Input 1
4 6
1 2
2 3
3 2
1 3
3 4
4 3
Sample Output 1
1
2
4
4
5
Explanation for Sample Output 1
- On day , user follows user . Nobody would follow anyone else in the social exchange event falling on the day, so the total sum is .
- On day , user follows user . Nobody would follow anyone else in the social exchange event falling on the day, so the total sum is .
- On day , user follows user . User would follow user in the social exchange event falling on the day. In this case, the total sum is and this is the largest possible value of the total sum.
- On day , user follows user . Nobody would follow anyone else in the social exchange event falling on the day, so the total sum is .
- On day , user follows user . Nobody would follow anyone else in the social exchange event falling on the day, so the total sum is .
- On day , user follows user . User would follow user , user would follow user , and user would follow user in the social exchange event falling on the day. In this case, the total sum is and this is the largest possible value of the total sum.
Sample Input 2
6 10
1 2
2 3
3 4
4 5
5 6
6 5
5 4
4 3
3 2
2 1
Sample Output 2
1
2
3
4
5
7
11
17
25
30
Comments