← 返回题目列表

AtCoder · abc120_d

D. 腐烂的桥梁

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有 N 岛屿和 M 桥梁。

的 i第桥连接 A_i-th 和 B_i双向岛屿。

最初,我们可以使用其中一些桥梁在任意两个岛屿之间旅行。

然而,调查结果显示,这些桥梁都会因老化而倒塌,按照从第一座桥到第二座桥的顺序 M第桥。

让 不便 是岛屿对的数量 (a, b) (a < b)这样我们就无法再在 a-th 和 b第一个岛屿使用剩余的一些桥梁。

对于每个 i (1 \leq i \leq M),发现不便之处就在 i第一座桥倒塌。

约束

  • 输入中的所有值都是整数。
  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq A_i < B_i \leq N
  • 所有对 (A_i, B_i) 是不同的。
  • 最初的不便之处在于 0.

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

输出

按顺序 i = 1, 2, ..., M,打印不便之处就在 i第一座桥倒塌。 请注意,答案可能不适合 32- 位整数类型。


示例输入 1

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

示例输出 1

0
0
4
5
6

例如,当第一至第三座桥梁垮塌时,带来的不便是 4 因为我们不能再在两对之间旅行 (1, 2), (1, 3), (2, 4) 和 (3, 4).


示例输入 2

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

示例输出 2

8
9
12
14
15

示例输入 3

2 1
1 2

示例输出 3

1