← 返回题目列表

Codeforces · 117/E

E. 树与否 树

中文机器翻译题面 查看原题

给定一个由 n 个顶点和 n 个边组成的无向连通图 G。 G 不包含自环或重边。让每条边都有两种状态:开和关。最初,所有边缘均关闭。

您还得到 m 个查询,表示为 (v, u) — 更改图 G 中从顶点 v 到顶点 u 的最短路径上所有边的状态。如果有多个这样的路径,则选择字典顺序最小的一个。更正式地说,让我们将从顶点 v 到顶点 u 的所有最短路径视为顶点 v、v1、v2、...、u 的序列。在这些序列中,我们选择字典顺序最小的一个。

在每次查询之后,您应该告诉有多少个连通分量具有其顶点与图 G 的顶点重合且边与图 G 的切换边重合的图。

输入

第一行包含两个整数 n 和 m (3 ≤ n ≤ 105, 1 ≤ m ≤ 105)。然后 n 条线将图的边描述为 a b (1 ≤ a, b ≤ n)。接下来的 m 行包含 v u (1 ≤ v, u ≤ n) 的查询。

保证图是连通的,没有任何自环或重边。

输出

打印 m 行,每行包含一个整数——查询结果。

示例

输入 #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

注意

让我们考虑第一个示例。我们将在图像上突出显示蓝色的打开边缘。

- 应用任何操作之前的图表。没有打开图边,这就是为什么最初有 5 个连接的组件。
- 查询 v = 5, u = 4 后的图。如果我们只考虑打开的边,我们可以看到该图具有三个分量。
- 查询 v = 1, u = 5 后的图。如果我们只考虑打开的边,我们可以看到该图具有三个分量。

两个具有相同长度的 k 个数字的序列的词典比较应按如下方式进行。如果存在这样的 i (1 ≤ i ≤ k),则序列 x 按字典顺序小于序列 y,因此 xi < yi,并且对于任何 j (1 ≤ j < i) xj = yj。