一般图最大匹配（Matching on General Graph）

问题描述

给定一个含 $N$ 个顶点、$M$ 条边的简单无向图，求其最大匹配——即边集的最大子集，使得任意两条边不共享顶点。

输出匹配的大小 $X$，以及所选边的端点对列表 $(a_0, b_0), (a_1, b_1), \dots, (a_{X-1}, b_{X-1})$。

约束条件

• $1 \leq N \leq 500$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• $0 \leq u_i, v_i < N$

输入格式

$N\ M$
$u_0\ v_0$
$u_1\ v_1$
:
$u_{M-1}\ v_{M-1}$

输出格式

$X$
$a_0\ b_0$
$a_1\ b_1$
:
$a_{X-1}\ b_{X-1}$

其中：

• $X$ 是最大匹配的边数；
• 每对 $(a_i, b_i)$ 是匹配中的一条边（顺序任意，且 $a_i < b_i$ 非必需）；
• 若存在多解，输出任意一种即可。

注：由于 $N \le 500$，可使用带花树（Blossom）算法求一般图最大匹配。

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

3
0 2
1 6
3 4

5 4
0 1
0 2
0 3
0 4

1
0 1