1059. Shortest Path Visiting All Nodes (Bitmask BFS)

Given a connected undirected graph with n nodes and a list of edges, return the length of the shortest path (number of edges) that visits every node at least once. You may start and end at any node and revisit nodes and edges. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Integer — the shortest covering path length.

Examples

Input: {"n":4,"edges":[[0,1],[0,2],[0,3]]}
Output: 4
Explanation: Traverse out and back through the center.

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

Input: {"n":3,"edges":[[0,1],[1,2],[0,2]]}
Output: 2
Explanation: A triangle needs two edges.

Constraints

• 1<=n<=12
• connected

Asked by