题目描述

有 $N$ 个结点和 $M$ 条无向边，第 $i$ 条边连接结点 $U_i$ 和 $V_i$。按照编号从小到大的顺序依次删除边。删除第 $i$ 条边后，编号 $1$ 到 $i$ 的边均不再存在。

两个不同结点无法互相到达时，它们构成一个不连通点对。请输出每次删边后的不连通点对数量。点对 $(x,y)$ 与 $(y,x)$ 视为同一个点对。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，每行包含两个整数 $U_i,V_i$，表示第 $i$ 条无向边。

输出格式

输出 $M$ 行，第 $i$ 行表示删除前 $i$ 条边后的不连通点对数量。

样例

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

0
0
3
5
6

数据范围与提示

• $2\le N\le10^5$
• $1\le M\le10^5$
• $1\le U_i<V_i\le N$
• 所有边互不相同