CHTCoder là một mạng xã hội đang được xây dựng, nơi bạn có thể chia sẻ những kỷ niệm với bạn bè. Trên CHTCoder, người dùng có thể theo dõi những người dùng khác. Ví dụ, nếu người dùng ~a~ theo dõi người dùng ~b~, thì người dùng ~a~ có thể đọc các bài đăng của người dùng ~b~ trên dòng thời gian của mình. Trong trường hợp này, có thể xảy ra việc người dùng ~b~ theo dõi lại người dùng ~a~ hoặc không. Tuy nhiên:

• Người dùng ~a~ không thể tự theo dõi chính mình.

• Người dùng ~a~ không thể theo dõi một người dùng ~b~ nhiều hơn một lần.

Có ~n~ người dùng, được đánh số từ ~1, 2, \dots, n~, bắt đầu sử dụng CHTCoder. Ban đầu, không có người dùng nào theo dõi bất kỳ người dùng nào khác.

Trong ~m~ ngày tiếp theo, các sự kiện theo dõi xảy ra như sau: Vào ngày thứ ~i~, người dùng ~a_i~ theo dõi người dùng ~b_i~ ~(1 \le i \le m)~.

Ban quản trị CHTCoder dự định tổ chức một sự kiện giao lưu xã hội trên dịch vụ này vào một thời điểm nào đó trong ~m~ ngày.

Sự kiện giao lưu diễn ra như sau:

1. Chọn một người dùng, gọi người dùng được chọn là ~x~.

2. Chọn một người dùng đang được ~x~ theo dõi tại thời điểm đó, gọi người dùng này là ~y~.

3. Chọn một người dùng ~z~ sao cho đồng thời thỏa mãn:

   • ~z~ khác ~x~;

   • ~x~ chưa theo dõi ~z~;

   • ~y~ đang theo dõi ~z~;

   • ~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.

Yêu cầu: Ban quản trị CHTCoder vẫn chưa quyết định sẽ tổ chức sự kiện giao lưu vào ngày nào. Vì vậy, họ muốn biết: Với mỗi ngày ~i~ ~(1 \le i \le m)~, nếu sự kiện giao lưu được tổ chức ngay sau sự kiện theo dõi của ngày thứ ~i~, thì tổng số lượt theo dõi của tất cả người dùng sau khi sự kiện giao lưu kết thúc là bao nhiêu?

Ta giả sử rằng sự kiện giao lưu xã hội hoàn thành trước khi sự kiện theo dõi của ngày tiếp theo diễn ra.

Input

• Dòng đầu tiên chứa ~2~ số nguyên dương ~n, m~ ~(2 \le n \le 10^5, 1 \le m \le 3 \cdot 10^5)~;

• ~m~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên dương ~a_i, b_i~, cho biết ngày thứ ~i~ người dùng ~a_i~ theo dõi người dùng ~b_i~ ~(1 \le a_i, b_i \le n)~. Các cặp ~(a_i, b_i)~ là đôi một khác nhau.

Output

Gồm ~m~ dòng, dòng thứ ~i~ ~(1 \le i \le m)~ in ra: Tổng số lượt theo dõi của tất cả người dùng sau khi sự kiện giao lưu xã hội kết thúc, nếu sự kiện giao lưu được tổ chức ngay sau sự kiện theo dõi của ngày thứ ~i~.

Scoring

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
9

Notes

Ngày ~1~: Người dùng ~1~ theo dõi người dùng ~2~. Trong sự kiện giao lưu, không có ai có thể theo dõi thêm người nào. Tổng số lượt theo dõi là ~1~.

Ngày ~2~: Người dùng ~2~ theo dõi người dùng ~3~. Không có ai có thể theo dõi thêm người nào. Tổng số lượt theo dõi là ~2~.

Ngày ~3~: Người dùng ~3~ theo dõi người dùng ~2~. Trong sự kiện giao lưu, người dùng ~1~ sẽ theo dõi người dùng ~3~. Khi đó tổng số lượt theo dõi là ~4~, đây là giá trị lớn nhất có thể đạt được.

Ngày ~4~: Người dùng ~1~ theo dõi người dùng ~3~. Không có ai có thể theo dõi thêm người nào. Tổng số lượt theo dõi là ~4~.

Ngày ~5~: Người dùng ~3~ theo dõi người dùng ~4~. Không có ai có thể theo dõi thêm người nào. Tổng số lượt theo dõi là ~5~.

Ngày ~6~: Người dùng ~4~ theo dõi người dùng ~3~. Trong sự kiện giao lưu:

• Người dùng ~1~ sẽ theo dõi người dùng ~4~;

• Người dùng ~2~ sẽ theo dõi người dùng ~4~;

• Người dùng ~4~ sẽ theo dõi người dùng ~2~.

Khi đó tổng số lượt theo dõi là ~9~, và đây là giá trị lớn nhất có thể đạt được.