题目描述

考虑一个 $2 \times n$ 的网格图，其节点为 $(x, y)$，其中 $x \in \{0, 1\}$，$y \in \{1, 2, \dots, n\}$。初始时图中含有 $3n - 2$ 条边，连接所有相邻的节点对。

你需要对该图进行动态维护，支持两类不同的调整操作。第一类操作形如 “$1\ x_0\ y_0\ x_1\ y_1$”，表示在节点 $(x_0, y_0)$ 与 $(x_1, y_1)$ 之间添加一条此前不存在的新边。第二类操作形如 “$2\ x_0\ y_0\ x_1\ y_1$”，表示删除节点 $(x_0, y_0)$ 与 $(x_1, y_1)$ 之间一条已有的边。

保证在每次调整中，$(x_0, y_0)$ 与 $(x_1, y_1)$ 在原网格图上是相邻的。即，要么它们拥有相同的 $x$ 坐标且 $|y_0 - y_1| = 1$，要么它们拥有相同的 $y$ 坐标且 $|x_0 - x_1| = 1$。每次调整后，我们保证图保持连通，你需要计算当前图中桥的数量。

输入格式

第一行输入一个整数 $T$（$1 \le T \le 1001$），表示测试用例的总数。对于每个测试用例，第一行包含整数 $n$（$1 \le n \le 200000$）和 $m$（$0 \le m \le 200000$）；$n$ 表示图的规模，$m$ 表示调整操作的次数。接下来的 $m$ 行，每行按上述格式描述一个调整操作。

只有一个测试用例满足 $n + m \ge 2000$。

输出格式

对于每个测试用例，输出 $m$ 行，每行包含一个整数，表示对应操作后图中桥的数量。

2
4 8
2 0 3 1 3
2 0 2 1 2
2 0 4 1 4
1 0 2 1 2
1 0 3 1 3
2 0 1 1 1
1 0 4 1 4
2 1 2 1 3
6 2
2 1 2 1 3
2 0 4 0 5

0
0
7
4
2
4
2
4
1
2

提示

翻译由 DeepSeek V3.2 完成