道路结组

一座园区有 $n$ 个路口，起初没有道路．接下来将依次修建 $q$ 条双向道路，每条道路连接两个不同的路口．

园区准备安排若干条巡检路线．每条路线恰好经过两条不同的道路，而且这两条道路必须在某个路口相接．例如，若已有连接 $u,v$ 的道路和连接 $v,w$ 的道路，就可以安排一条 $u\to v\to w$ 的巡检路线．

同一条道路不能被两条巡检路线使用，但不同路线可以经过相同的路口．不要求使用全部道路．

每修好一条道路，请求出：使用当前已有的道路，最多能同时安排多少条巡检路线？

每次只计算最多能安排的路线数量，不会占用或删除道路．计算下一次答案时，可以重新安排全部路线，不必保留之前的方案．

输入格式

第一行输入两个整数 $n,q$，分别表示路口数和修建道路的次数．路口编号为 $1$ 到 $n$．

接下来 $q$ 行，每行两个整数 $u_i,v_i$，表示第 $i$ 次修建连接这两个路口的道路．

输出格式

输出 $q$ 行，第 $i$ 行为修好前 $i$ 条道路后，最多能同时安排的巡检路线数量．

样例 1

4 4
1 2
2 3
3 1
3 4

0
1
1
2

只修好第一条道路时，无法安排包含两条道路的路线，答案为 $0$．

修好第二条道路后，可以安排路线 $1\to2\to3$，答案为 $1$．修好第三条道路后，一共只有三条道路，仍然最多安排一条路线．

修好第四条道路后，可以同时安排以下两条路线：

• $1\to2\to3$，使用第 $1,2$ 条道路．
• $1\to3\to4$，使用第 $3,4$ 条道路．

两条路线虽然都经过路口 $1$ 和 $3$，但没有使用同一条道路，因此合法，答案为 $2$．

更多样例

• Data/sample1.in 与 Data/sample1.ans：上面的题面样例．
• Data/sample2.in 与 Data/sample2.ans：$n=11,q=16$，满足子任务 1．
• Data/sample3.in 与 Data/sample3.ans：$n=q=2000$，满足子任务 2．
• Data/sample4.in 与 Data/sample4.ans：$n=200000,q=199999$，满足子任务 3．
• Data/sample5.in 与 Data/sample5.ans：$n=q=200000$，该样例无特殊限制．
• Data/sample6.in 与 Data/sample6.ans：$n=q=10$，满足子任务 1．
• Data/sample7.in 与 Data/sample7.ans：$n=200000,q=160007$，满足子任务 3．
• Data/sample8.in 与 Data/sample8.ans：$n=q=200000$，该样例无特殊限制．

下发样例供本地测试使用，通过全部下发样例不代表解法正确，也不保证获得某个子任务的分数．

点击下载本题选手目录

数据范围与子任务

对于所有测试数据，$2\le n\le2\times10^5$，$1\le q\le2\times10^5$，$1\le u_i,v_i\le n$ 且 $u_i\ne v_i$．整张图是简单图，即没有两次加入端点相同的道路，端点的先后顺序不影响道路是否相同．图可以不连通，也可以包含没有连接任何道路的路口．

各子任务独立计分，只有通过该子任务的全部测试点才能获得对应分数．

子任务	分值	特殊性质
1	12	$q\le16$
2	18	$n,q\le2000$
3	20	最终得到的图是一片森林，即不含环的无向图
4	50	无特殊性质