KOI 市由 $N$ 栋建筑组成，编号为 $1$ 到 $N$；并有 $M$ 条双向道路，编号为 $1$ 到 $M$，连接这些建筑。每条道路连接两栋不同的建筑；具体而言，第 $i$ 条道路双向连接建筑 $u_i$ 与建筑 $v_i$。可以通过道路在任意两栋建筑之间通行。

最初，KOI 市的所有道路都可以免费通行，即每条道路的通行费为 $0$。然而，为了克服城市的财政困难，市长 Jeong-ol 计划在接下来的 $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)$$

Jeong-ol 希望分析通行费变化对市民的影响。请你帮助 Jeong-ol，分别计算每个 $i$ 在第 $i$ 天结束后道路网络的总费用。

限制

所有给定的值均为整数。

• $2 \le N \le 500$
• $N - 1 \le M$
• 对于 $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 分) 无额外限制

输入格式

第一行包含两个整数 $N$ 和 $M$，以空格分隔。

接下来 $M$ 行描述道路。第 $i$ 行（$1 \le i \le M$）包含两个整数 $u_i$ 与 $v_i$，以空格分隔。

输出格式

共输出 $M$ 行。第 $i$ 行（$1 \le i \le M$）应输出第 $i$ 天结束后道路网络的总费用。

样例数据

样例数据 1

输入

4 4
1 2
2 3
3 1
3 4

输出

0
6
10
16

说明

4 天后，建筑之间的最小出行费用可以用下表表示：

因此，在第 4 天结束后，道路网络的总费用为 [ 0 + 1 + 1 + 2 + 1 + 0 + 1 + 2 + 1 + 1 + 0 + 1 + 2 + 2 + 1 + 0 = 16。 ]

样例数据 2

输入

4 4
2 3
3 1
3 4
1 2

输出

0
8
14
16