学校有 $n$ 间教室，编号为 $1$ 到 $n$。每对教室之间都恰好有一条走廊直接相连，但为了交通便利，这些走廊对学生而言是单向的。

学校秘书必须将备忘录送到每间教室的班长手中（每间教室恰好有一名班长）。他有一个绝妙的主意来减轻工作量——他可以将多份备忘录交给某位班长，并委托该班长代为分发。如果一位班长能够通过走廊到达另一间教室，并能通过走廊回到自己所在的教室，那么他就可以将备忘录送到那间教室。班长愿意完成尽可能多的分发任务——前提是只要在完成所有任务后，他们能够回到自己的教室即可。

如果秘书可以将备忘录分配给集合中的班长，并委托他们进行分发，使得每间教室都能收到一份备忘录，那么这个班长集合就被称为“完备的”。请找出完备集合的最小可能大小。

实际上，你需要处理 $q$ 次更新。在初始设置中，对于每对满足 $1 \le i < j \le n$ 的 $(i, j)$，连接教室 $i$ 和 $j$ 的单向走廊方向是从 $i$ 指向 $j$（即你可以从编号较小的教室前往编号较大的教室）。随后，每次更新都会反转一条单向走廊的方向——请在每次更新后给出完备集合的最小可能大小。

输入格式

第一行包含两个整数 $n$ 和 $q$。 接下来的 $q$ 行中，第 $k$ 行包含两个整数 $u_k$ 和 $v_k$。第 $k$ 次更新将反转连接教室 $u_k$ 和 $v_k$ 的单向走廊的方向。

• $1 \le n, q \le 5 \cdot 10^5$
• $1 \le u_k < v_k \le n$

输出格式

对于每次更新，输出一行，包含一个整数，表示更新后完备集合的最小大小。

样例

输入 1

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

输出 1

4
2
1
1
2

说明

请参考以下图片，查看第二次和第四次更新后教室路径的样子：

• 第二次更新后，秘书可以将 3 份备忘录交给 3 班班长，将 1 份备忘录交给 1 班班长。3 班班长可以将备忘录送到 2 班和 4 班的班长手中，然后回到 3 班。
• 第四次更新后，秘书可以将 4 份备忘录交给 4 班班长。4 班班长可以将备忘录送到所有其他班长手中，然后回到 4 班。