题目描述

读完一篇关于增量拓扑序和强连通分量维护的论文后，程远给自己出了一个实验题。

一开始有一张包含 $n$ 个点的有向图，图中没有任何边。随后会进行 $m$ 次操作。每次操作先向图中加入一条给定的有向边，然后你需要回答当前图中有多少对点 $(u,v)$ 满足：

• $1\le u<v\le n$；
• $u$ 可以到达 $v$；
• $v$ 也可以到达 $u$。

换句话说，每次加边后，你需要统计所有位于同一个强连通分量中的无序点对数量。

请你在所有操作之后依次输出每次的答案。

输入格式

第一行包含两个整数 $n,m$，表示点数和操作次数。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示本次新加入一条从 $u$ 指向 $v$ 的有向边。

输入允许重边和自环。

输出格式

输出 $m$ 行，第 $i$ 行表示加入第 $i$ 条边后，满足条件的点对数量。

数据范围

• $1\le n\le 10^5$；
• $1\le m\le 2.5\cdot 10^5$；
• $1\le u,v\le n$。

样例 1

输入

4 6
1 2
2 3
2 1
3 4
4 3
3 2

输出

0
0
1
1
2
6