1111. General Graph Maximum Matching

Given a general undirected graph with n nodes and edges, return the size of the maximum matching — the largest set of edges no two of which share a vertex. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Integer — the maximum matching size.

Examples

Input: {"n":4,"edges":[[0,1],[1,2],[2,3],[3,0]]}
Output: 2
Explanation: Two disjoint edges match all four nodes.

Input: {"n":3,"edges":[[0,1],[1,2],[2,0]]}
Output: 1
Explanation: An odd triangle matches only one edge.

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

Constraints

• 1<=n<=18

Asked by