当前没有测试数据。

题目描述

某大型物流公司在全国建设了 $N$ 个配送中心，并通过 $M$ 条高速货运通道连接了所有的配送中心，所有配送中心，互相可达。第 $i$ 条通道连接了编号为 $U_i$ 和 $V_i$ 的两个配送中心，所有通道都可双向通行。

由于基础设施逐渐老化，通道在未来可能会出现故障无法使用。为了预测通道故障之后，对于整个配送网络带来的损失，物流公司决定进行故障模拟。

模拟的方式为，按照通道编号 $1$ 至 $M$ 的顺序，依次模拟每条通道故障之后，对于整个配送网络的影响。请注意：当模拟完编号为 $i$ 的通道出现故障之后，继续模拟编号为 $i+1$ 的通道出现故障时，编号为 $1 \sim i$ 的通道依然处于故障状态。

我们定义故障指数，为某个时刻，互相无法到达的配送中心对的数量。即：如果两个编号为 $X$ 和 $Y$（$X < Y$）的配送中心如果互相无法到达，则故障指数 $+1$。

请你按顺序计算并输出，模拟每一条通道因故障暂停运行之后，故障指数的数值。

输入格式

第一行输入两个整数 $N$ 和 $M$，表示配送中心数量和通道数量。

接下来的 $M$ 行中，每行两个整数 $U_i$ 和 $V_i$，表示编号为 $i$ 条通道连接的两个配送中心编号。

输出格式

输出共 $M$ 行，第 $i$ 行一个整数，表示当编号 $1 \sim i$ 之间的通道因故障暂停运行后的故障指数。

样例 #1

输入

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

输出

0
0
3
5
6

数据范围

对于所有的测试数据，满足 $2 \le N \le 10^5$，$1 \le M \le 10^5$，$1 \le U_i < V_i \le N$，所有 $(U_i, V_i)$ 互不相同。