Joitter là một mạng xã hội đang thịnh hành, nơi bạn có thể chia sẻ những kỷ niệm với bạn bè.

Trên Joitter, người dùng có thể theo dõi những người dùng khác. Chẳng hạn, khi người dùng \(a\) theo dõi người dùng \(b\), \(a\) có thể đọc các bài đăng của \(b\) trên dòng thời gian. Khi đó, \(b\) có thể theo dõi lại \(a\) hoặc không. Tuy nhiên, một người dùng không thể theo dõi chính mình và không thể theo dõi cùng một người dùng khác nhiều hơn một lần.

Có \(N\) người dùng, được đánh số từ \(1\) đến \(N\), vừa bắt đầu sử dụng Joitter. Ban đầu, không ai theo dõi ai.

Trong \(M\) ngày tiếp theo, vào ngày thứ \(i\) (\(1 \le i \le M\)), người dùng \(A_i\) bắt đầu theo dõi người dùng \(B_i\).

Ban quản lý Joitter dự định tổ chức một sự kiện giao lưu đúng một lần trong \(M\) ngày này. Sự kiện diễn ra như sau:

1. Chọn một người dùng, gọi là \(x\).
2. Chọn một người dùng mà \(x\) đang theo dõi, gọi là \(y\).
3. Chọn một người dùng \(z\) thỏa mãn: \(z\) khác \(x\), \(x\) chưa theo dõi \(z\), \(y\) đang theo dõi \(z\), và \(z\) đang theo dõi \(y\).
4. Cho \(x\) theo dõi \(z\).
5. Lặp lại các bước trên cho đến khi không thể chọn được bộ ba \((x,y,z)\) nào nữa.

Ban quản lý chưa quyết định ngày tổ chức sự kiện. Vì vậy, với mỗi \(i\) (\(1 \le i \le M\)), họ muốn biết giá trị lớn nhất của tổng số người được theo dõi bởi từng người dùng sau sự kiện, nếu sự kiện được tổ chức ngay sau khi \(A_i\) theo dõi \(B_i\) vào ngày thứ \(i\). Sự kiện được giả sử là kết thúc trước hành động theo dõi vào ngày tiếp theo.

Các thời điểm tổ chức được xét riêng biệt; trong mỗi trường hợp chỉ có một sự kiện giao lưu. Cho số người dùng và các hành động theo dõi trong \(M\) ngày, hãy tính các giá trị lớn nhất nói trên.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo dạng sau. Tất cả các giá trị đều là số nguyên.

N M
A_1 B_1
...
A_M B_M

Dữ liệu ra

In ra \(M\) dòng. Dòng thứ \(i\) (\(1 \le i \le M\)) chứa giá trị lớn nhất của tổng số người được theo dõi bởi từng người dùng sau sự kiện giao lưu, nếu sự kiện được tổ chức ngay sau hành động theo dõi của ngày thứ \(i\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le M \le 300\,000\).
• \(1 \le A_i \le N\) với \(1 \le i \le M\).
• \(1 \le B_i \le N\) với \(1 \le i \le M\).
• \(A_i \ne B_i\) với \(1 \le i \le M\).
• \((A_i,B_i) \ne (A_j,B_j)\) với \(1 \le i < j \le M\).

Phân nhóm

1. (1 điểm) \(N \le 50\).
2. (16 điểm) \(N \le 2000\).
3. (83 điểm) Không có ràng buộc bổ sung.

Ví dụ

4 6
1 2
2 3
3 2
1 3
3 4
4 3

1
2
4
4
5
9

6 10
1 2
2 3
3 4
4 5
5 6
6 5
5 4
4 3
3 2
2 1

1
2
3
4
5
7
11
17
25
30

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi thứ 2. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.