Có n hòn đảo được nối bởi m cây cầu, cây cầu thứ i nối liền hai thành phố u_i và v_i. Tuy nhiên, do được xây dựng đã lâu, các cây cầu không còn vững và sẽ bắt đầu sập, theo trình tự từ cây cầu thứ nhất đến cây cầu thứ m.

Ta định nghĩa độ bất tiện là số cặp hòn đảo (x, y) với 1 \leq x < y \leq n sao cho từ hòn đảo x không thể đi đến thành phố y bằng những cây cầu chưa bị sập.

Với mỗi i từ 1 đến m, hãy tính độ bất tiện sau khi các cây cầu có thứ tự từ 1 đến i bị sập.

• Dòng thứ nhất ghi hai số nguyên n, m ; (2 \leq n \leq 200000, 1 \leq m \leq 200000) – số hòn đảo và số cây cầu.
• m dòng tiếp theo, dòng thứ i gồm hai số nguyên u_i và v_i (1 \leq u < v \leq n) - mô tả cây cầu thứ i. Dữ liệu vào đảm bảo giá trị các cặp (u_i, v_i) là phân biệt nhau đôi một.

Gồm m dòng, dòng thứ i là độ bất tiện sau khi các cây cầu có thứ tự từ 1 đến i bị sập.

• Subtask 1 (50% số test): n, m \leq 2000
• Subtask 2 (50% số test): Không có ràng buộc gì thêm

Ví dụ, sau khi các cây cầu thứ 1, 2, 3 bị sập thì có 6 cặp thành phố không đi được đến nhau: (1, 3), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5).