CF117E.Tree or not Tree

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.

给你一个包含 $n$ 个顶点和 $n$ 条边的无向连通图 $G$。图 $G$ 中不含自环或重边。每条边具有两种状态：“开启”（on）和“关闭”（off）。初始时，所有边均处于“关闭”状态。

你还会收到 $m$ 个查询，每个查询表示为 $(v,\,u)$ —— 将图 $G$ 中从顶点 $v$ 到顶点 $u$ 的最短路径上的所有边的状态取反（即：开启变关闭，关闭变开启）。若存在多条这样的最短路径，则选择字典序最小的一条。更准确地说，将所有从顶点 $v$ 到顶点 $u$ 的最短路径视作顶点序列 $v,\,v_1,\,v_2,\,\dots,\,u$；在所有这些序列中，选取字典序最小的一个。

每次查询后，请输出由图 $G$ 的全部顶点以及当前所有“开启”边所构成的子图的连通分量数量。

The first line contains two integers n and m (3 ≤ n ≤ 105, 1 ≤ m ≤ 105). 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.

第一行包含两个整数 $n$ 和 $m$（$3 \leq n \leq 10^5$，$1 \leq m \leq 10^5$）。接下来的 $n$ 行描述图的边，每行为 $a\ b$（$1 \leq a,\ b \leq n$）。随后的 $m$ 行为查询，每行为 $v\ u$（$1 \leq v,\ u \leq n$）。

保证该图是连通的，且不含自环或重边。

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

输出 m 行，每行包含一个整数——查询结果。

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.

我们来考虑第一个样例。我们将在图中用蓝色高亮显示已开启的边。

• 执行任何操作前的图。此时图中没有任何边被开启，因此初始时有 5 个连通分量。

  

• 执行查询 $v = 5,\ u = 4$ 后的图。若仅考虑已开启的边，则图中有三个连通分量。

  

• 执行查询 $v = 1,\ u = 5$ 后的图。若仅考虑已开启的边，则图中有三个连通分量。

  

对两个长度均为 $k$ 的数字序列进行字典序比较，应按如下方式进行：当且仅当存在某个下标 $i$（$1 \le i \le k$），使得 $x_i < y_i$，且对任意 $j$（$1 \le j < i$）均有 $x_j = y_j$ 时，称序列 $x$ 字典序小于序列 $y$。