题目描述

有 $n$ 个社团成员，编号为 $1\sim n$。最开始有 $m$ 条双向联系，第 $i$ 条联系连接两个不同成员，且任意两名成员之间至多有一条直接联系。

接下来，这 $m$ 条联系会按照输入顺序一条一条失效。每失效一条联系后，原本在同一个联系圈中的成员可能被分开。

请你输出从初始状态开始，以及每次失效之后，当前一共有多少个连通的成员圈。

输入格式

第一行包含两个整数 $n,m$，表示成员数量和联系数量。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示一条联系连接成员 $u$ 和成员 $v$。保证 $u\ne v$，且无重边。

输出格式

输出 $m+1$ 行。

第 $i$ 行表示前 $i-1$ 条联系已经失效后，当前的连通块数量。

样例

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

1
1
2
2
3
4

样例说明

初始时所有成员在同一个联系圈中。按顺序删除联系后，连通块数量依次变为 $1,2,2,3,4$，因此连同初始状态共输出 $6$ 行。

数据范围

对于 $50\%$ 的数据，$2\le n,m\le 1000$。

对于 $100\%$ 的数据，$2\le n\le 10^5$，$1\le m\le 2\times 10^5$。