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