<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>

from collections import deque
from itertools import permutations

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        min_path_length = float('inf')
        for i in range(len(graph)):
            min_path_i = self.shortestPath2(graph, i)
            min_path_length = min(min_path_length, min_path_i)
        return min_path_length
    
    def shortestPath(self, graph, src, dest):
        queue = deque()
        visited = set()
        
        queue.append(src)
        visited.add(src)
        length = 0
        while queue:
            size = len(queue)
            for i in range(size):
                cur = queue.popleft()
                if cur == dest:
                    return length
                for node in graph[cur]:
                    if not node in visited:
                        queue.append(node)
                        visited.add(node)
            length += 1
        return float('inf')

    def shortestPath2(self, graph: List[List[int]], src: int):
        queue = deque()
        src_tup = (src, (1 << src))
        queue.append(src_tup)
        visited = {src_tup}
        dest_mask = 2**(len(graph)) - 1
        length = 0
        while queue:
            size = len(queue)
            for i in range(size):
                cur = queue.popleft()
                if cur[1] == dest_mask:
                    return length
                for node in graph[cur[0]]:
                    node_tup = (node, cur[1] | (1 << node))
                    if not node_tup in visited:
                        queue.append(node_tup)
                        visited.add(node_tup)
            length += 1
        return float('inf')

        
18600