1374. Cover All Nodes with Minimum Edges (Bitmask)

Given an undirected graph with n nodes numbered 0 to n-1 and a list of edges, choose the fewest edges so that every node is an endpoint of at least one chosen edge. Return that minimum count, or -1 if no such selection exists because some node has no incident edge.

Input: A JSON object {"n": <node count>, "edges": [[u, v], ...]}.

Output: Return the minimum number of edges covering every node, or -1 when impossible.

Examples

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

Input: {"n":3,"edges":[[0,1]]}
Output: -1
Explanation: Node 2 has no incident edge, so it is impossible -> -1.

Constraints

• 1 <= n <= 16
• 0 <= u, v < n and u != v

Asked by