题目描述
有一条长为$n$的链，链上的点编号依次为$1,2,...,n$
给定$m$次加边操作，每次加入一条边$(x,y)$
每次加边操作后，求图中有多少对边（两条不同的边），满足删去后图不连通
两对边不同当且仅当存在某条边在一对中而不在另一对中
输入格式
第一行两个整数$n,m$
接下来$m$行，每行两个整数$x,y$
输出格式
共$m$行，每行一个整数，表示答案
样例1
见下发文件 $\rm A/ex\_A1.in$ 和 $\rm A/ex\_A1.ans$
最终的两种方案分别$(1,2),(1,2)$和$(3,5),(4,5)$
样例2
见下发文件 $\rm A/ex\_A2.in$ 和 $\rm A/ex\_A2.ans$
样例3
见下发文件 $\rm A/ex\_A3.in$ 和 $\rm A/ex\_A3.ans$
数据范围
$1\le n,m\le 2\times 10^{5}$，$1\le x,y\le n$
Subtask1（10分）：$1 \le n,m\le 100$
Subtask2（20分）：$1 \le n,m\le 2\times 10^{3}$
Subtask3（30分）：$1 \le x \le \lfloor\frac{n}{2}\rfloor < y\le n$
Subtask4（40分）：无特殊限制