P10080 [GDKOI2024 提高组] 匹配

给定一个 $2n$ 个点 $m$ 条边的二分图，左部点编号为 $1 \sim n$，右部点编号为 $n + 1 \sim 2n$。 给定每条边为黑色或白色，你需要找到一个完美匹配，使得匹配里的黑色边数恰好为偶数。 如果你对二分图的定义有疑问： - 二分图是一个无向图，点分为左右两部分，每部分各 $n$ 个点，每条边都连接两个属于不同部分的点。 - 一个完美匹配是一个大小为 $n$ 的边的集合，使得每个点都恰好与集合里的一条边相连。

无

无

**【样例解释】** 在第一组数据中，一个合法的完美匹配是 $(1, 6),(2, 5),(3, 4)$，且里面有恰好两条黑色边。 在第二组数据中，虽然存在完美匹配，但每个完美匹配都有奇数条黑色边。 **【数据范围】** **本题使用子任务捆绑测试。** 对于所有数据，保证 $1 \leq T \leq 250$，$2 \leq n,\sum n \leq 500$，$1 \leq m \leq n^2$。保证图中不存在重边，即对于 $i \neq j$ 有 $(u_i, v_i)\neq (u_j , v_j)$。 - Subtask 1（20%）：$n ≤ 8$，$T ≤ 10$。 - Subtask 2（20%）：$n ≤ 18$，$T ≤ 10$。 - Subtask 3（20%）：$c_i$ 在 $\{0, 1\}$ 里独立均匀随机。 - Subtask 4（40%）：无特殊限制。