P14284 [ICPC 2025 WF] Delivery Service

里海城际包裹公司（ICPC）即将在里海附近的各个城市间启动包裹递送服务。公司计划雇佣快递员在这些城市间运送包裹。 每位快递员都有一个家乡城市和一个目的地城市，而且所有快递员的日程完全相同：他们在 9:00 从家乡城市出发，12:00 到达目的地城市，14:00 从目的地城市出发，17:00 返回家乡城市。当快递员在家乡或目的地城市时，他们可以从客户那里接收包裹或向客户递送包裹。他们也可以与同时在该城市的其他快递员交接包裹。由于 ICPC 是一家个性化服务公司，包裹永远不会被放在仓库或其他设施等候后续领取——除非包裹已经到达目的地，否则快递员要么自己随身保管包裹（白天或晚上），要么将其交给另一个快递员。 公司会安排快递员的交接，使得任何包裹最终都能投递到目的地。至少理论上是这样！我们称两个城市 $u$ 和 $v$ 是连通的，若能将包裹从城市 $u$ 递送到城市 $v$，并能从 $v$ 递送回 $u$。为了评估其雇佣效率，公司希望在每雇佣一名快递员后，统计此时有多少对城市 $(u, v)$ 是连通的（$1 \le u < v \le n$）。

输入的第一行包含两个整数 $n$ 和 $m$，其中 $n$（$2 \le n \le 2 \cdot 10^5$）为城市总数，$m$（$1 \le m \le 4 \cdot 10^5$）为总共将要雇佣的快递员数。快递员按雇佣顺序编号 1 到 $m$。接下来有 $m$ 行，第 $i$ 行包含两个不同的整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$），表示第 $i$ 位快递员的家乡和目的地城市。

输出 $m$ 个整数，第 $i$ 个整数表示前 $i$ 位快递员雇佣完成后，连通的城市对 $(u, v)$（$1 \le u < v \le n$）的数量。

**样例 1 说明：** 1. 招聘第 1 位快递员后，城市 1 和 2 连通。 2. 招聘第 2 位快递员后，城市 2 和 3 连通。但城市 1 和 3 依然不连通。即使有快递员往返 1、2 和 2、3，彼此之间永远不会相遇。 3. 招聘第 3 位快递员后，城市 3 和 4 连通，城市 2 和 4 也连通。例如，将包裹从城市 2 递送到城市 4 的一种方式如下： - 19:00 将包裹交给第 2 位快递员（在城市 2）； - 第 2 位快递员次日 12:00 抵达城市 3，并把包裹交给同样在城市 3 的第 3 位快递员； - 18:00，第 3 位快递员将包裹递送到城市 4。 4. 招聘第 4 位快递员后，所有六组城市都是连通的。 由 ChatGPT 5 翻译