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