P16312 [ICPC 2023 Jinan R] 我只想要…多一个…

在编写完论文《Sandpile Prediction on Structured Undirected Graphs》后，小青鱼想要所有人都多多解决图论问题。“没有图论问题我们便活不下去，所有人都应该来做沙堆预测问题！” 二分图是一张满足如下条件的图：它的节点可以被分成两个不相交的集合 $U$ 与 $V$，使得图中的每一条边都连接 $U$ 中的一个节点与 $V$ 中的一个节点。如果 $U$ 与 $V$ 中节点的数量相同，则称这张图为平衡二分图。 无向图的匹配是一个边的集合，其中任意两条边都没有共同的端点。图的最大匹配是一个包含了最多条边的匹配。图的匹配数是这张图的最大匹配所包含的边的数量。 现在，小青鱼给了您一张平衡二分图。您需要添加恰好一条边，连接 $U$ 中的一个节点与 $V$ 中的一个节点，使得图的匹配数增加。求方案数。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据： 第一行输入两个整数 $n$ 与 $m$（$1 \le n,m \le 10^5$）表示 $U$ 与 $V$ 的节点数量以及边的数量。 对于接下来 $m$ 行，第 $i$ 行输入两个整数 $u_i$ 与 $v_i$（$1 \le u_i, v_i \le n$），表示第 $i$ 条边连接 $U$ 中第 $u_i$ 个节点与 $V$ 中第 $v_i$ 个节点。图可能有重边。 保证所有数据 $(n + m)$ 之和不超过 $4 \times 10^5$。

每组测试数据输出一行一个整数表示答案。

对于第一组样例数据，原图的匹配数为 $2$。通过添加边 $(1, 1)$，$(1, 4)$，$(2, 1)$，$(2, 4)$，$(3, 1)$ 或 $(3, 4)$，我们可以将匹配数增加到 $3$。所以答案为 $6$。 对于第二组样例数据，原图的匹配数为 $3$。显然我们无法增加匹配数，因为所有的节点都已经在匹配之中，所以答案为 $0$。 对于第三组样例数据，原图的匹配数为 $1$。通过添加边 $(2, 1)$，$(2, 3)$，$(3, 1)$ 或 $(3, 3)$，我们可以将匹配数增加到 $2$。所以答案为 $4$。