class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) 
    {
        if (S==T) return 0;
        
        unordered_map<int,vector<int>>stop2routes;
        for (int i=0; i<routes.size(); i++)        
            for (int j=0; j<routes[i].size(); j++)
                stop2routes[routes[i][j]].push_back(i);
        
        queue<pair<int,int>>q;
        unordered_set<int>visitedRoutes;
        unordered_set<int>visitedStops;
        for (auto route: stop2routes[S])
        {
            q.push({route,1});
            visitedRoutes.insert(route);
            visitedStops.insert(S);
        }            
        
        while (!q.empty())
        {
            int curRoute = q.front().first;
            int step = q.front().second;
            q.pop();
            
            for (int stop: routes[curRoute])
            {
                if (stop==T) return step;
                if (visitedStops.find(stop)!=visitedStops.end()) continue;
                    
                visitedStops.insert(stop);
                for (int nextRoute: stop2routes[stop])
                {
                    if (visitedRoutes.find(nextRoute)!=visitedRoutes.end())
                        continue;
                    visitedRoutes.insert(nextRoute);
                    q.push({nextRoute,step+1});
                }
            }            
        }
        return -1;
    }
};