事实上，当 호반우 到达异世界时，他的一举一动就已经通过直播平台 Twitch 在地球上进行了直播。

在当前的直播画面中，可以看到 호반우 正在探索一个地下城，这里每天都会刷新 $1$ 到 $N$ 号，共 $N$ 只大小为 1 的史莱姆。

作为直播唯一的观众，상호 打算在 $M$ 天里，每天使用一次“Twip”的老虎机，在 호반우 到达之前将史莱姆合并。

转动老虎机后，会得到一对正整数 $a, b$（满足 $1 \le a < b \le N$），并将其存入背包，用于每天合并史莱姆。

使用一对正整数 $a, b$ 时，会将 $a$ 号史莱姆所属的史莱姆群体与 $b$ 号史莱姆所属的史莱姆群体合并。如果 $a$ 号史莱姆和 $b$ 号史莱姆已经属于同一个史莱姆群体，则不会进行合并。

合并后史莱姆的大小为：$($合并前两个史莱姆群体的大小之和$)+($合并后的史莱姆群体中包含的初始史莱姆数量$)$。

상호 想知道每天地下城中所有史莱姆的大小之和最大能达到多少。作为主播，请告诉这位唯一的观众答案吧！

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $M$，分别表示史莱姆的数量和 상호 转动老虎机的天数。$(2 \le N \le 200\,000, 1 \le M \le 300\,000)$

接下来的 $M$ 行，每行按顺序给出 상호 每天转动老虎机得到的正整数对 $a, b$。$(1 \le a < b \le N)$

输出格式

输出 $M$ 行。

第 $i$ 行输出在第 $i$ 天转动老虎机后，地下城中所有史莱姆的大小之和的最大值。

样例

样例输入 1

2 1
1 2

样例输出 1

3

样例输入 2

2 2
1 2
1 2

样例输出 2

3
3