Migrated from Lutece 2533 交通要塞

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

大家好，今天小编和大家介绍云南的一个小县城，它是世界上最窄的城市，大家好奇吗？现在就让小编带着大家一起来看看吧。为什么说这个县城是世界上最窄的城市，小编也很好奇，所以为什么它是世界上最窄的城市呢，可能因为它很窄，所以是世界上最窄的城市吧。事实上它确实就是世界上最窄的城市，并且它就是云南的一个小县城，名字叫做延津县，位于云南省的东北部，它长成如下所示的样子：

从上面图片中容易发现这个城市被一条河流割据，河两岸的建筑依靠桥梁连接。现在小编为了简化模型，考虑延津县最开始是如下所示的样子：

在上图所示的简化模型中，中间是河流，两岸通过若干个桥梁相连接。延津县的最左边是一个大桥梁，最右边也是一个大桥梁，同一岸上的相邻两个建筑之间用则一条笔直的公路连接，并且每个桥梁的两端都恰好有建筑，所有建筑也只位于桥梁的两端。

现在县长觉得很多路是无用的，为了节约维修桥梁和公路的经费，县长打算拆掉一些公路和桥梁，以节约政府的财政支出。然而有一个比较头疼的事就是，如果拆除不当，可能会导致有两个建筑无法互相到达，因此县长请来了小编。

小编告诉县长，为了拆除一些桥梁或公路，可能还需要建一些其它公路，县长觉得非常有道理。于是经过小编的指点，县长已经能够保证每次操作不会导致两个建筑无法互相到达，但县长仍然担心整个城市的交通是否会因为拆除某些道路而变得拥挤。

对于一条公路或桥梁而言，如果某些建筑必须通过它才能到达其它某个建筑，那么县长认为这条公路或桥梁是交通要塞，这并不是一件好事，因此县长想知道每次他拆除掉或增建桥梁后整个城市有多少个交通要塞。小编也无能为力，所以到底该怎么计算有多少个交通要塞呢，小编就带大家一起来看看吧，但是其实小编也不知道正确答案，所以小编把这个任务交给了你，你能帮县长和小编解决这个问题吗。

Input

第一行输入一个整数 $T$，代表接下来会有 $T$ 组数据。

对于每组数据而言，第一行输入两个整数 $n,q\ (2\le n\le 2\times 10^5,1\le q\le 2\times 10^5)$，代表两岸各有 $n$ 个建筑，初始的时候两岸相对的建筑都有一条桥梁连接，同岸相邻建筑有一条公路连接，上岸的建筑按从左到右顺序用编号 $1,2,3,\ldots ,n$，下岸的建筑按从左到右顺序用编号 $n+1,n+2,\ldots ,n+n$ 表示，接下来县长会有 $q$ 次道路拆迁或建设。

县长的每次操作都是下述四种格式之一：

• $\texttt{1 i}$：代表建立一个连接建筑 $i$ 到建筑 $n+i$ 的桥；
• $\texttt{2 i}$：代表建立一个连接建筑 $i$ 到 $i+1$ 的公路；
• $\texttt{-1 i}$：代表摧毁一个连接建筑 $i$ 到建筑 $n+i$ 的桥；
• $\texttt{-2 i}$：代表摧毁一个连接建筑 $i$ 到 $i+1$ 的公路。

保证 $T$ 组数据的 $n+q$ 的总和不超过 $4\times 10^5$。

Output

对于县长的每次操作，都输出当前操作执行后整个城市的交通要塞个数。

Samples

2
4 8
-1 3
-1 2
-1 4
1 2
1 3
-1 1
1 4
-2 6
6 2
-2 8
-2 4

0
0
7
4
2
4
2
4
1
2

Resources

2021 UESTC ICPC Training for Data Structures