5085：故障指数
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：1
解决：0
题目描述
# 故障指数
## 题目描述
某大型物流公司在全国建设了 $N$ 个配送中心，并通过 $M$ 条高速货运通道连接了所有的配送中心，所有配送中心，互相可达。第 $i$ 条通道连接了编号为 $U_i$ 和 $V_i$ 的两个配送中心，所有通道都可**双向通行**。
由于基础设施逐渐老化，通道在未来可能会出现故障无法使用。为了预测通道故障之后，对于整个配送网络带来的损失，物流公司决定进行故障模拟。
模拟的方式为，**按照通道编号 $1$ 至 $M$ 的顺序**，依次模拟每条通道故障之后，对于整个配送网络的影响。请注意：当模拟完编号为 $i$ 的通道出现故障之后，继续模拟编号为 $i+1$ 的通道出现故障时，编号为 $1 \sim i$ 的通道**依然处于故障状态**。
我们定义**故障指数**，为某个时刻，互相无法到达的配送中心对的数量。即：如果两个编号为 $X$ 和 $Y$ （ $X \lt Y$ ）的配送中心如果互相无法到达，则故障指数 $+1$ 。
请你按顺序计算并输出，模拟每一条通道因故障暂停运行之后，故障指数的数值。
## 输入格式
第一行输入两个整数 $N$ 和 $M$ ，表示配送中心数量和通道数量。
接下来的 $M$ 行中，每行两个整数 $U_i$ 和 $V_i$ ，表示编号为 $i$ 条通道连接的两个配送中心编号。
## 输出格式
输出共 $M$ 行，第 $i$ 行一个整数，表示当编号 $1 \sim i$ 之间的通道因故障暂停运行后的故障指数。
## 样例
### 样例输入 1
```text
4 5
1 2
2 3
3 4
1 4
2 4
```
### 样例输出 1
```text
0
0
3
5
6
```
### 样例输入 2
```text
8 12
1 2
1 3
2 5
2 6
2 3
3 4
4 5
5 6
5 8
6 8
6 7
7 8
```
### 样例输出 2
```text
0
7
7
7
13
18
22
22
25
25
27
28
```
### 样例输入 3
```text
26 25
7 10
9 12
1 5
14 15
14 19
8 26
2 21
21 25
1 20
3 14
4 14
6 22
14 23
1 15
17 24
4 26
2 11
16 18
14 18
14 21
17 21
10 15
14 22
9 10
13 23
```
### 样例输出 3
```text
25
49
72
162
179
195
223
236
240
252
272
281
295
298
304
305
306
311
315
319
320
322
323
324
325
```
## 说明/提示
样例 $1$ 说明
初始状态下，所有配送中心互相可达。
- 当第 $1$ 条连接配送中心 $1$ 和 $2$ 的通道故障之后，所有配送中心依然互相可达，故障指数为 $0$ 。
- 当第 $2$ 条连接配送中心 $2$ 和 $3$ 的通道故障之后，所有配送中心依然互相可达，故障指数为 $0$ 。
- 当第 $3$ 条连接配送中心 $3$ 和 $4$ 的通道故障之后，互相不可达的配送中心有 $(1,2)$ $(2,3)$ $(2,4)$ 共 $3$ 个，故障指数为 $3$ 。
- 当第 $4$ 条连接配送中心 $1$ 和 $4$ 的通道故障之后，互相不可达的配送中心有 $(1,2)$ $(1,3)$ $(1,4)$ $(2,3)$ $(3,4)$ 共 $5$ 个，故障指数为 $5$ 。
- 当第 $5$ 条连接配送中心 $2$ 和 $4$ 的通道故障之后，所有配送中心互相不可达，故障指数为 $6$ 。
数据范围
对于所有的测试数据，满足 $2 \leq N \leq 10^5$ ， $1 \leq M \leq 10^5$ ， $1 \leq U_i \lt V_i \leq N$ ，所有 $(U_i, V_i)$ 互不相同。
| 测试点 | 数据范围 |
|---|---|
| $1 \sim 7$ | $1 \le N,M \le 100$ |
| $8 \sim 25$ | $1 \le N,M \le 10^5$ |
---
**题目来源：** 25年6月-C组（大咖）