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ố ui và vi. 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 ≤ x < y ≤ 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ữ liệu

• Dòng thứ nhất ghi hai số nguyên n, m (2 ≤ n ≤ 200000, 1 ≤ m ≤ 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 ui và vi (1 ≤ u < v ≤ n) - mô tả cây cầu thứ i. Dữ liệu vào đảm bảo giá trị các cặp (ui, vi) là phân biệt nhau đôi một.

Kết quả

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.

Sample Input

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

Sample Output

0
6
6
7
9
10