Tree or not Tree

题意翻译

G是一张由n个点和n条边组成的无向图。G中没有自环和重边。每条边有两种状态“开”和“关”。一开始，所有的边都是“关”着的。 现在有m个操作(v,u)，表示将从v到u的最短路上的边改变状态（如果状态为“开”则变成“关”，反之，变成“开”）。如果v到u存在多条最短路，则我们选取点序列字典序最小的那一条。 比如，将所有从v到u的路径上的点表示成序列为 v，v1，v2，...，u 。那么我们从中取字典序最小的那一条。 在每一次操作后，你需要计算在图中由所有点和状态为“开”的边所组成图的连通块的数目。 样例解释： 在图中处于“开”状态的边我们用蓝色高亮表示。 在没有进行任何操作前，所有的边都是“关”，也就是说，一开始有5个连通块。  下图是执行了操作v＝5，u＝4后的图。如果我们关心“开”的边，可以看到有3个连通块。  然后执行操作v＝1，u＝5后，如下图。同样如果我们关心“开”的边，可以看到有3个连通块。  两个长度为k的点序列比较方法如下。 存在两个序列x，y，长度都是k。 如果存在i(1≤i≤k)和任意j(1≤j＜i)使得 xi＜yi 并且 xj＝yj ，那么我们就说x比y小。 Input 单组测试数据 第一行有两个整数，n和m(3≤n≤10^5，1≤m≤10^5). 接下来的n行， 每行有两个整数a，b(1≤a,b≤n)表示a到b有边相连。 再接下来有m行， 每行有两个整数v，u(1≤v,u≤n)表示一次操作，即要变化的路径的起点和终点。 所给定的图是连通的，里面没有自环，也没有重边。 Output 有m行，每行代表一次操作后，连通块数目。

题目描述

You are given an undirected connected graph $ G $ consisting of $ n $ vertexes and $ n $ edges. $ G $ contains no self-loops or multiple edges. Let each edge has two states: on and off. Initially all edges are switched off. You are also given $ m $ queries represented as $ (v,u) $ — change the state of all edges on the shortest path from vertex $ v $ to vertex $ u $ in graph $ G $ . If there are several such paths, the lexicographically minimal one is chosen. More formally, let us consider all shortest paths from vertex $ v $ to vertex $ u $ as the sequences of vertexes $ v,v_{1},v_{2},...,u $ . Among such sequences we choose the lexicographically minimal one. After each query you should tell how many connected components has the graph whose vertexes coincide with the vertexes of graph $ G $ and edges coincide with the switched on edges of graph $ G $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 3<=n<=10^{5} $ , $ 1<=m<=10^{5} $ ). Then $ n $ lines describe the graph edges as $ a $ $ b $ ( $ 1<=a,b<=n $ ). Next $ m $ lines contain the queries as $ v $ $ u $ ( $ 1<=v,u<=n $ ). It is guaranteed that the graph is connected, does not have any self-loops or multiple edges.

输出格式

Print $ m $ lines, each containing one integer — the query results.

输入输出样例

输入样例 #1

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

输出样例 #1

3
3

输入样例 #2

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

输出样例 #2

4
3

说明

Let's consider the first sample. We'll highlight the switched on edges blue on the image. - The graph before applying any operations. No graph edges are switched on, that's why there initially are 5 connected components.  - The graph after query $ v=5,u=4 $ . We can see that the graph has three components if we only consider the switched on edges.  - The graph after query $ v=1,u=5 $ . We can see that the graph has three components if we only consider the switched on edges.  Lexicographical comparison of two sequences of equal length of $ k $ numbers should be done as follows. Sequence $ x $ is lexicographically less than sequence $ y $ if exists such $ i $ ( $ 1<=i<=k $ ), so that $ x_{i}<y_{i} $ , and for any $ j $ ( $ 1<=j<i $ ) $ x_{j}=y_{j} $ .