P13519 [KOI 2025 #2] 通行费

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

KOI 市由从 1 号到 $N$ 号的 $N$ 座建筑组成，有从 1 号到 $M$ 号的 $M$ 条双向道路连接着各个建筑。每条道路连接两座不同的建筑，其中第 $i$ 条道路双向连接着 $u_i$ 号建筑和 $v_i$ 号建筑。此时，可以利用这些道路在任意两座建筑之间往来。 原本 KOI 市的各条道路都可以免费使用，即所有道路的通行费都为 0 元。但是，KOI 市的市长“郑信息”为了克服 KOI 市的财政困难，决定在 $M$ 天内对各条道路征收通行费。具体来说，“郑信息”在第 $i$ 天会将第 $i$ 条道路的通行费变更为 1 元。因此，当 $M$ 天全部过去后，所有道路的通行费都将变为 1 元。 从 $a$ 号建筑到 $b$ 号建筑的**最小移动成本**定义为从 $a$ 号建筑移动到 $b$ 号建筑所需支付的通行费总和的最小值，并记作 $f(a, b)$。如果 $a=b$，则 $f(a, b)=0$。 路网的**总成本**定义为所有可能的建筑对之间的最小移动成本之和。即，计算所有满足 $1 \le a, b \le N$ 的自然数 $a$ 和 $b$ 的 $f(a, b)$ 值，然后将它们全部相加，得到的就是路网的总成本。用数学符号表示，路网的总成本为 $\sum_{a=1}^{N} \sum_{b=1}^{N} f(a, b)$。 “郑信息”想要分析通行费的变化会对市民产生怎样的影响。你需要帮助“郑信息”，计算出第 $i$ 天结束后路网的总成本，对每一个 $i$ (从 1 到 $M$) 都进行计算。

第一行给定 $N$ 和 $M$，以空格分隔。 接下来 $M$ 行是道路的信息。其中第 $i(1 \le i \le M)$ 行给定两个整数 $u_i, v_i$，以空格分隔。

共输出 $M$ 行。其中第 $i(1 \le i \le M)$ 行，输出第 $i$ 天结束后路网的总成本。

### 样例 1 解释 4 天后，各建筑间的最小移动成本可以用下表表示。 | | **1 号建筑** | **2 号建筑** | **3 号建筑** | **4 号建筑** | | :------- | :----------: | :----------: | :----------: | :----------: | | **1 号建筑** | 0 | 1 | 1 | 2 | | **2 号建筑** | 1 | 0 | 1 | 2 | | **3 号建筑** | 1 | 1 | 0 | 1 | | **4 号建筑** | 2 | 2 | 1 | 0 | 因此，第 4 天结束后，路网的总成本为表中所有数字之和： $0 + 1 + 1 + 2 + 1 + 0 + 1 + 2 + 1 + 1 + 0 + 1 + 2 + 2 + 1 + 0 = 16$。 ### 限制条件 * 所有给定的数都是整数。 * $2 \le N \le 500$ * $N-1 \le M \le \frac{N(N-1)}{2}$ * 对于 $1 \le i \le M$，满足 $u_i \ne v_i$。 * 对于 $1 \le i \le M$，满足 $1 \le u_i, v_i \le N$。 * 连接任意两座不同建筑的道路最多只有一条。 * 可以利用道路在任意两座建筑之间往来。 ### 子任务 1. (10 分) $N \le 5$。 2. (15 分) $N \le 50$。 3. (30 分) $M \le 500$。 4. (45 分) 无额外限制条件。