[AdditionalFile6987.zip](file://AdditionalFile6987.zip?type=additional_file)

#6987. 「ICPC World Finals 2025」快递服务

标签: 传统 | 时间限制: 12000 ms | 内存限制: 2048 MiB |

题目描述

里海城际包裹公司（ICPC）正在开办一项快递服务，将在里海附近的各个城市之间递送包裹。该公司计划雇佣快递员在这些城市之间运送包裹。

每位快递员都有一个出发城市和一个目的地城市，并且所有快递员的行程安排完全相同：他们在 9:00 离开出发城市，12:00 到达目的地城市，14:00 离开目的地城市，17:00 返回出发城市。当快递员在他们的出发城市或目的地城市时，他们可以从客户那里接收包裹和/或向客户递送包裹。他们也可以将包裹交接给或从同时在同一城市的其他快递员那里接收包裹。由于 ICPC 是一项个性化服务，包裹绝不会被留在仓库或其他设施中等待稍后取件——除非包裹已到达其最终目的地，否则快递员必须要么自己保管包裹（无论白天还是晚上），要么将其交接给另一位快递员。

公司将指导快递员以某种方式交接包裹，使得任何包裹总能被送到目的地。至少他们是这么希望的！如果可以从城市 $u$ 向城市 $v$ 递送包裹，并且也可以从 $v$ 向 $u$ 递送包裹，我们就称这两个城市 $u$ 和 $v$ 是连通的。为了评估招聘流程的效率，公司希望在每雇佣一位快递员后，计算出连通的城市对 $(u, v)$ $(1 \leq u < v \leq n)$ 的数量。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，其中 $n$ $(2 \leq n \leq 2 \cdot 10^{5})$ 是城市的数量，$m$ $(1 \leq m \leq 4 \cdot 10^{5})$ 是将要雇佣的快递员数量。快递员按雇佣顺序从 $1$ 到 $m$ 编号。接下来是 $m$ 行，第 $i$ 行包含两个不同的整数 $a_{i}$ 和 $b_{i}$ $(1 \leq a_{i}, b_{i} \leq n)$，分别表示快递员 $i$ 的出发城市和目的地城市。

输出格式

输出 $m$ 个整数，分别表示在雇佣了前 $1, 2, \ldots, m$ 位快递员后，连通的城市对的数量。

样例

输入

4 4
1 2
2 3
4 3
4 2

输出

1
2
4
6

1. 雇佣第一位快递员后，城市 $1$ 和 $2$ 是连通的。
2. 雇佣第二位快递员后，城市 $2$ 和 $3$ 是连通的。但是请注意，城市 $1$ 和 $3$ 仍然不是连通的。尽管有一位快递员在城市 $1$ 和 $2$ 之间移动，另一位在城市 $2$ 和 $3$ 之间移动，但他们永远不会在同一时间出现在同一城市。
3. 雇佣第三位快递员后，城市 $3$ 和 $4$ 是连通的，城市 $2$ 和 $4$ 也是连通的。例如，一种从城市 $2$ 向城市 $4$ 递送包裹的方式是：
   • 晚上 19:00 在城市 $2$ 将包裹交给快递员 $2$；
   • 第二天，快递员 $2$ 在 12:00 到达城市 $3$，并将包裹交给同样在城市 $3$ 的快递员 $3$；
   • 晚上 18:00，快递员 $3$ 将包裹送达城市 $4$。
4. 雇佣第四位快递员后，所有六对城市都变得连通了。