1083. Bipartite Matching — Maximum Matching

Given a bipartite graph with n left nodes (0..n-1), m right nodes (0..m-1), and edges [u, v] connecting left node u to right node v, return the size of the maximum matching (the largest set of edges with no shared endpoint). The input is JSON {n, m, edges}.

Input: JSON {n, m, edges}.

Output: Integer — the maximum matching size.

Examples

Input: {"n":3,"m":3,"edges":[[0,0],[0,1],[1,0],[2,2]]}
Output: 3
Explanation: A perfect matching of size 3.

Input: {"n":2,"m":2,"edges":[[0,0],[1,1]]}
Output: 2
Explanation: Two independent edges.

Input: {"n":1,"m":1,"edges":[]}
Output: 0
Explanation: No edges.

Constraints

• 1<=n,m<=500

Asked by