每次先配一对能配上的，为什么最后反而少配一个？

"""Research prototype: maximum cardinality matching in small bipartite graphs.

Python standard library only. Partitions are explicit and indexed separately.
The algorithm accepts at most six vertices per side; exhaustive checks stop at
three per side. This is neither weighted matching nor a performance benchmark.
"""
from itertools import product
import json
from pathlib import Path
import platform


def normalize(left_count, right_count, edges):
    if any(type(n) is not int or not 0 <= n <= 6 for n in (left_count, right_count)):
        raise ValueError("partition sizes must be integers in 0..6")
    clean = []
    for edge in edges:
        if not isinstance(edge, (list, tuple)) or len(edge) != 2:
            raise ValueError("each edge needs one index from each partition")
        u, v = edge
        if (type(u) is not int or type(v) is not int
                or not 0 <= u < left_count or not 0 <= v < right_count):
            raise ValueError("edge outside its explicit partitions")
        if (u, v) in clean:
            raise ValueError("simple graph expected; duplicate edge")
        clean.append((u, v))
    return sorted(clean)


def maximum_matching(left_count, right_count, edges):
    edges = normalize(left_count, right_count, edges)
    adjacent = [[] for _ in range(left_count)]
    for u, v in edges:
        adjacent[u].append(v)
    owner = [-1] * right_count
    trace = []

    def reroute(u, seen):
        if u in seen:
            return False
        seen.add(u)
        for v in adjacent[u]:
            if owner[v] == -1 or reroute(owner[v], seen):
                owner[v] = u
                return True
        return False

    for u in range(left_count):
        # A visited set belongs to this one search, not to the whole algorithm.
        if reroute(u, set()):
            pairs = sorted((left, right) for right, left in enumerate(owner) if left != -1)
            trace.append({"start_left": u, "pairs_after_augmentation": pairs})
    return sorted((u, v) for v, u in enumerate(owner) if u != -1), trace


def first_free_greedy(left_count, right_count, edges):
    edges = normalize(left_count, right_count, edges)
    used_left, used_right, chosen = set(), set(), []
    for u, v in edges:
        if u not in used_left and v not in used_right:
            chosen.append((u, v))
            used_left.add(u)
            used_right.add(v)
    return chosen


def assignment_oracle(left_count, right_count, edges):
    """Independent reference: enumerate each left vertex's partner or -1.

    No DFS, alternating path or right-owner updates are used here.
    """
    allowed = set(edges)
    best, vectors = 0, 0
    for assignment in product(range(-1, right_count), repeat=left_count):
        vectors += 1
        pairs = [(u, v) for u, v in enumerate(assignment) if v != -1]
        if (len({v for _, v in pairs}) == len(pairs)
                and all(pair in allowed for pair in pairs)):
            best = max(best, len(pairs))
    return best, vectors


def valid_witness(pairs, edges):
    return (len({u for u, _ in pairs}) == len(pairs)
            and len({v for _, v in pairs}) == len(pairs)
            and all(pair in edges for pair in pairs))


def main():
    example = [(0, 0), (0, 1), (1, 0)]
    greedy = first_free_greedy(2, 2, example)
    best, trace = maximum_matching(2, 2, example)
    assert len(greedy) == 1 and len(best) == 2
    graph_count = assignment_vectors = greedy_shortfalls = 0
    for nl in range(4):
        for nr in range(4):
            universe = [(u, v) for u in range(nl) for v in range(nr)]
            for mask in range(1 << len(universe)):
                edges = [edge for bit, edge in enumerate(universe) if mask & (1 << bit)]
                pairs, _ = maximum_matching(nl, nr, edges)
                optimum, inspected = assignment_oracle(nl, nr, edges)
                assert valid_witness(pairs, edges)
                assert len(pairs) == optimum
                g = first_free_greedy(nl, nr, edges)
                assert valid_witness(g, edges) and len(g) <= optimum
                greedy_shortfalls += len(g) < optimum
                assignment_vectors += inspected
                graph_count += 1
    report = {
        "status": "PASS", "python_version": platform.python_version(),
        "example_edges": example, "greedy": greedy, "maximum": best,
        "augmentation_trace": trace, "graphs_compared": graph_count,
        "assignment_vectors_inspected": assignment_vectors,
        "greedy_shortfall_graphs": greedy_shortfalls,
        "scope": "All labeled simple bipartite graphs for each left/right size in 0..3; only cardinality and witness validity compared. No weighted/general graph matching, NetworkX run, or timing claims."
    }
    Path(__file__).with_suffix('.report.json').write_text(
        json.dumps(report, ensure_ascii=False, indent=2) + '\n', encoding='utf-8')
    print(f"greedy={greedy}; maximum={best}")
    print(f"graphs_compared={graph_count}; assignment_vectors={assignment_vectors}; greedy_shortfalls={greedy_shortfalls}")
    print("PASS; exhaustive scope: labeled bipartite partitions 0..3 each")


if __name__ == '__main__':
    main()