1383. Shortest Path Visiting All Nodes

Given an undirected connected graph as an adjacency list, find the length of the shortest walk that visits every node at least once. You may start and stop at any node, and you may revisit nodes and edges as often as you like.

Input: A JSON object {"graph": [[neighbours of node 0], [neighbours of node 1], ...]}.

Output: Return the number of edges in the shortest walk visiting all nodes.

Examples

Input: {"graph":[[1,2,3],[0],[0],[0]]}
Output: 4
Explanation: The centre must be revisited between leaves, needing 4 moves.

Input: {"graph":[[1],[0,2,4],[1,3,4],[2],[1,2]]}
Output: 4
Explanation: A walk of length 4 covers every node.

Constraints

• 1 <= n <= 12
• the graph is connected and undirected

Asked by