背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

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$ 天结束后路网的总成本。

4 4
1 2
2 3
3 1
3 4

0
6
10
16

4 4
2 3
3 1
3 4
1 2

0
8
14
16

提示

样例 1 解释

4 天后，各建筑间的最小移动成本可以用下表表示。

因此，第 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 分) 无额外限制条件。