1227. Shortest Path Visiting All Nodes (BFS + Bitmask)

Given an undirected connected graph as an adjacency list, return the length of the shortest walk that visits every node. You may start and stop at any node and may revisit nodes and edges. The input is JSON {graph}.

Input: JSON {graph}.

Output: Integer — the length of the shortest such walk.

Examples

Input: {"graph":[[1,2,3],[0],[0],[0]]}
Output: 4
Explanation: A star graph needs four steps.

Input: {"graph":[[1],[0,2,4],[1,3,4],[2],[1,2]]}
Output: 4
Explanation: Four steps suffice.

Input: {"graph":[[]]}
Output: 0
Explanation: Single node.

Constraints

• 1<=n<=12

Asked by