统计(count)
题目描述
给定一颗基环外向树(n点n边无自环无重边的无向连通图)。
每条边有开和关两种状态,起初所有边均为关闭状态。
有m次操作,每次操作将$u$到$v$的最短路径(路径长度相同则选择字典序最小的路径)上的边的状态全部反转。并输出只有打开的边有效的情况下,这张图共有多少个连通块。
输入格式
一行两个正整数$N,M$。 接下来n行,每行两个数$u_i,v_i$表示$u_i,v_i$之间有一条边。
接下来$m$行,每行两个数$u_i,v_i$表示一次操作。
输出格式
每个操作输出$m$行,每行一个整数,即连通块个数。
输入样例
5 2
2 1
4 3
2 4
2 5
4 1
5 4
1 5
输出样例
3
3
数据规模和约定
对于$30$%的数据 $3 \leq n \leq 1000,1 \leq m \leq 1000$
对于$100$%的数据$3 \leq n \leq 10^5,1 \leq m \leq 10^5$