P17066 [ICPC 2017 Shenyang R] Bridge

Consider a $2 \times n$ grid graph with nodes $(x, y)$ where $x \in \{0, 1\}$ and $y \in \{1, 2, \dots, n\}$. The initial graph has $3n - 2$ edges connecting all pairs of adjacent nodes. You need to maintain the graph with two types of different adjustments. The first one, denoted by “$1\ x_0\ y_0\ x_1\ y_1$”, adds a new edge between the nodes $(x_0, y_0)$ and $(x_1, y_1)$ which did not exist. The second one, denoted by “$2\ x_0\ y_0\ x_1\ y_1$”, erases an existing edge between the nodes $(x_0, y_0)$ and $(x_1, y_1)$. It is sure that, for each adjustment, $(x_0, y_0)$ and $(x_1, y_1)$ were adjacent in the original grid graph. That is, they either share the same $x$ coordinate and $|y_0 - y_1| = 1$, or they share the same $y$ coordinate and $|x_0 - x_1| = 1$. After each adjustment, we guarantee the connectedness of the graph, and you need to calculate the number of bridges in the current graph.

The first line of input contains an integer $T$ ($1 \le T \le 1001$) which is the total number of test cases. For each test case, the first line contains integers $n$ ($1 \le n \le 200000$) and $m$ ($0 \le m \le 200000$); $n$ indicates the size of the graph and $m$ is the number of adjustments. Each of the following $m$ lines contains an adjustment described as above. Only one case satisfies $n + m \ge 2000$.

For each test case, output $m$ lines, each of which contains the number of bridges.