class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)

        # Edge case: If there's only 1 node, path length is 0
        if n == 1:
            return 0

        # The final state we want (all bits set to 1)
        # Example: if n = 3, ending_mask = 111 (binary) = 7
        ending_mask = (1 << n) - 1

        # Queue for BFS: (current_node, current_mask, distance)
        queue = deque()

        # Set to keep track of visited states: (current_node, current_mask)
        # This prevents us from doing redundant work or getting stuck in loops
        seen = set()
        # Initialize BFS from all nodes
        # We can start anywhere, so we treat all nodes as possible starting points
        for i in range(n):
            initial_mask = 1 << i
            queue.append((i, initial_mask, 0))
            seen.add((i, initial_mask))

        while queue:
            node, mask, dist = queue.popleft()

            # Check if we've visited all nodes
            if mask == ending_mask:
                return dist
            
            # Traverse neighbors
            for neighbor in graph[node]:
                new_mask = mask | (1 << neighbor)

                # If we haven't been at this neighbor with this specific path history
                if (neighbor, new_mask) not in seen:
                    seen.add((neighbor, new_mask))
                    queue.append((neighbor, new_mask, dist + 1))
        return -1 # If the graph is connected, this won't happen