There are N cities in a country and M roads are connected these cities. The i-th road connects u and v cities bidirectionally. Initially, yoy can travel between any two cities using one/more roads. The roads will damage due to aging after some time.
Let inconvinience be the number of pairs of roads ( u<v) such that we are no longer able to travel between u and v using remaining roads.
For each i (1<=i<=N), find the inconvinience just after the i-th road damages. Inconvinience is initially 0.

Example:
4 5
1 2
3 4
1 3
2 3
1 4

output: 0 0 4 5 6
Explanation: When first three roads are damaged, inconvinience is 4 since we can't travel between (1,2), (1,3), (2,4), and (3,4).