847

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        unordered_map<int, set<int>> vis;
        queue<pair<int, int>> q;
        int mask = 0;

        // Special case of 1 node.
        if(graph.size() == 1) return 0;

        // Assume (mask of visited, current node) as state of BFS.
        // Push initial states in queue.
        for(int i=0; i<graph.size(); i++){
            int newMask = mask | (1<<i);
            q.push({newMask, i});
            vis[newMask].insert(i);
        }

        int steps = 0;
        while(!q.empty()){
            int sz = q.size();
            for(int i=0; i<sz; i++){
                auto p = q.front(); q.pop();
                int mask = p.first, node = p.second;

                // Push new states in queue if not visited.
                for(auto child: graph[node]){
                    int newMask = mask | (1<<child);
                    if(newMask == ((1<<graph.size())-1))
                        return steps+1;
                    if(vis[newMask].count(child)) continue;
                    q.push({newMask, child});
                    vis[newMask].insert(child);
                }

            }
            steps++;
        }
        return steps;
    }
};