Bobo 正在研究 ICPCCamp 的道路历史。在 ICPCCamp 中，有 $n$ 个城市和 $m$ 条双向道路。第 $i$ 条道路连接第 $a_i$ 个城市和第 $b_i$ 个城市。

最初没有道路。最终，道路按 $1, 2, \dots, m$ 的顺序建成。

Bobo 想知道在第 $i$ 条道路建成后，有多少对城市之间存在“奇数路径”（odd drive）。城市 $u$ 和 $v$ 之间存在奇数路径，当且仅当存在某个正整数 $k$ 以及序列 $v_1, v_2, \dots, v_{2k}$，使得 $v_1 = u$，$v_{2k} = v$，且对于所有 $1 \le i < 2k$，城市 $v_i$ 和 $v_{i+1}$ 之间都有一条道路。允许经过同一个城市多次。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n, m \le 10^5$)。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n$)。

输出格式

输出 $m$ 行，每行一个整数 $w_1, w_2, \dots, w_m$，其中 $w_i$ 表示在第 $i$ 条道路建成后，存在奇数路径的城市对数量。

样例

样例输入 1

3 3
1 2
2 3
3 1

样例输出 1

1
2
3

样例输入 2

4 3
1 2
3 4
2 3

样例输出 2

1
2
4