翻译

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行，每行代表一次操作后，连通块数目。