给定一个由 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。