分数: 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