统计(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$