<p>You have an undirected, connected graph of <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code>. You are given an array <code>graph</code> where <code>graph[i]</code> is a list of all the nodes connected with node <code>i</code> by an edge.</p>

<p>Return <em>the length of the shortest path that visits every node</em>. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/12/shortest1-graph.jpg" style="width: 222px; height: 183px;" />
<pre>
<strong>Input:</strong> graph = [[1,2,3],[0],[0],[0]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> One possible path is [1,0,2,0,3]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/12/shortest2-graph.jpg" style="width: 382px; height: 222px;" />
<pre>
<strong>Input:</strong> graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> One possible path is [0,1,4,2,3]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == graph.length</code></li>
	<li><code>1 &lt;= n &lt;= 12</code></li>
	<li><code>0 &lt;= graph[i].length &lt;&nbsp;n</code></li>
	<li><code>graph[i]</code> does not contain <code>i</code>.</li>
	<li>If <code>graph[a]</code> contains <code>b</code>, then <code>graph[b]</code> contains <code>a</code>.</li>
	<li>The input graph is always connected.</li>
</ul>

############################################################
# Exam.py
# Author: Jagadeesh Vasudevamurthy
# Copyright: Jagadeesh Vasudevamurthy 2024
###########################################################

########################################
#Nothing can be changed in class Exam
########################################
class Exam:
    def __init__(self, g:'list of list of size 3', s:'start', ans:'empty list', work:'list of size 1', show:'Bool')->'None':
        self._g = g # graph
        self._s = s  # start city
        self._ans = ans # YOU NEED TO FILL
        self._work = work
        self._show = show
        

        ## YOU CAN has any number of private varibles and functions starts
        
        ## YOU CAN has any number of private varibles and functions ends

        ## Must write this routine
        self._alg()

    def _increment_work(self)->'None':
        self._work[0] += 1

    ### WRITE CODE BELOW #################

    def _alg(self)->'None':
        n = len(self._g)
        if n == 1:
            self._ans.append([self._s])
            return
        
        # Initialize BFS with bitmasking
        queue = deque((i, 1 << i, 0) for i in range(n))
        visited = [[False] * (1 << n) for _ in range(n)]
        
        for i in range(n):
            visited[i][1 << i] = True
        
        while queue:
            node, mask, dist = queue.popleft()
            
            # If all nodes are visited
            if mask == (1 << n) - 1:
                self._ans.append([dist])
                return
            
            # Explore neighbors
            for neighbor in self._g[node]:
                # Ensure `neighbor` is an integer (node index)
                if isinstance(neighbor, list):
                    neighbor = neighbor[0]  # Extract the first element if it's a list
                
                next_mask = mask | (1 << neighbor)
                if not visited[neighbor][next_mask]:
                    visited[neighbor][next_mask] = True
                    queue.append((neighbor, next_mask, dist + 1))
        
        # If no valid path found (which shouldn't happen)
        self._ans.append([-1])

    def _display_results(self) -> None:
        # Optionally display the results
        if self._show and self._ans:
            print(f"Shortest path length to visit all nodes starting from {self._s}: {self._ans[0][0]}")
class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        # Initialize variables for the Exam class
        start_node = 0  # You can start from any node, here we start from node 0
        ans = []
        work = [0]
        show = False  # Set to True if you want to see the debug output

        # Instantiate the Exam class with the graph and other parameters
        exam = Exam(graph, start_node, ans, work, show)
        
        # Return the result from the Exam class
        return exam._ans[0][0]

17700