问题描述

思考完数学，上官觉得神清气爽，要不找个地方上班？于是他找到了地图，想看看哪里比较适合自己去。但是由于多年来的高速发展，地图早已千变万化，其中有 $n$ 个城市两两之间连通。执拗的上官不想根据这份地图走，他想要看看所有历史版本的地图。

意外地，他想起隔壁淳平的家里有一张写着历年来的地图变化情况的纸，恰好就是关于这 $n$ 个城市的。于是上官要来了这份图纸，上面描述了这 $n$ 个城市从初始状态 一条路都没有 到如今 两两连通 的状态，都建了哪些路，以及每条路连接的两个城市是什么。因此上官又有了个坏点子。

他把每个城市画成一个点，编号为 $1$ 到 $n$，而道路按照时间倒序编号设置为 $1$ 到 $m$，即 $1$ 为最新的路，$m$ 为最旧的路。现在上官想一点点推出原来的地图，即对 $i \in [1, \space m]$，在删去 $[1, \space i]$ 的路后，剩下的城市里，有多少城市对 $(u, \space v)$ 满足 $u$ 与 $v$ 不连通（$u \lt v$）。可是他不想浪费时间，想尽快上路，你能帮他算算吗？

$u$ 与 $v$ 连通：$u$ 与 $v$ 可以通过图中的一些边相互到达。

$u$ 与 $v$ 不连通：$u$ 与 $v$ 通过图中的任意边都无法相互到达。

输入输出格式

输入格式

第一行为两个正整数 $n$，$m$，分别代表城市的数量和边的数量。

第二行到第 $m + 1$ 行，每行两个整数 $a_i$，$b_i$，$1 \leqslant i \leqslant m$，表示 $a_i$ 和 $b_i$ 之间连接了一条道路，按照时间倒序给出。

保证在 $m$ 条路全加入的情况下，$1$ 到 $n$ 两两连通。

$$2 \leqslant n \leqslant 100000, \space 1 \leqslant m \leqslant 100000$$$$1 \leqslant a_i, \space b_i \leqslant n$$

输出格式

输出 $m$ 行，每行一个整数，表示当前有多少城市对 $(u, \space v)$ 满足 $u$ 与 $v$ 不连通（$u \lt v$）。

更正式地说，第 $i$ 行输出的数，是删去 $[1, \space i]$ 的路后，剩下的城市里，有多少城市对 $(u, \space v)$ 满足 $u$ 与 $v$ 不连通（$u \lt v$），$1 \leqslant i \leqslant m$。

测试样例

4 5
1 2
3 4
1 3
2 3
1 4

0
0
4
5
6

2 1
1 2

1