<p>You are given an array <code>routes</code> representing bus routes where <code>routes[i]</code> is a bus route that the <code>i<sup>th</sup></code> bus repeats forever.</p>

<ul>
	<li>For example, if <code>routes[0] = [1, 5, 7]</code>, this means that the <code>0<sup>th</sup></code> bus travels in the sequence <code>1 -&gt; 5 -&gt; 7 -&gt; 1 -&gt; 5 -&gt; 7 -&gt; 1 -&gt; ...</code> forever.</li>
</ul>

<p>You will start at the bus stop <code>source</code> (You are not on any bus initially), and you want to go to the bus stop <code>target</code>. You can travel between bus stops by buses only.</p>

<p>Return <em>the least number of buses you must take to travel from </em><code>source</code><em> to </em><code>target</code>. Return <code>-1</code> if it is not possible.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> routes = [[1,2,7],[3,6,7]], source = 1, target = 6
<strong>Output:</strong> 2
<strong>Explanation:</strong> The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
<strong>Output:</strong> -1
</pre>

<p>&nbsp;</p>

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

<ul>
	<li><code>1 &lt;= routes.length &lt;= 500</code>.</li>
	<li><code>1 &lt;= routes[i].length &lt;= 10<sup>5</sup></code></li>
	<li>All the values of <code>routes[i]</code> are <strong>unique</strong>.</li>
	<li><code>sum(routes[i].length) &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= routes[i][j] &lt; 10<sup>6</sup></code></li>
	<li><code>0 &lt;= source, target &lt; 10<sup>6</sup></code></li>
</ul>

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {

        if( source == target )
            return 0;

        unordered_map< int, unordered_set< int> > routesOfStop;

        unordered_map< int, unordered_set< int> > stopsOfRoute;

        for( int i = 0 ; i < routes.size() ; i++ ){
            for( auto stop : routes[i] ){
                routesOfStop[stop].insert( i );

                stopsOfRoute[i].insert( stop );
            }
        }

        unordered_set<int> visitedStops, visitedRoutes;

        // unordered_map< int, unordered_set< int> > routesOfStop;

        queue<int> cur_q, next_q;

        // visitedStops.insert( source );

        for( auto route : routesOfStop[source] ){

            cur_q.push( route );

            visitedRoutes.insert( route );
        }


        int len = 1;


        while( !cur_q.empty() ){

            int r = cur_q.front();

            // cout << r << "\n";

            cur_q.pop();

            if( stopsOfRoute[r].count( target ) )
                return len;

            for( auto stop : stopsOfRoute[r] ){

                if( visitedStops.count( stop ) )
                    continue;

                visitedStops.insert( stop );

                for( auto next_r : routesOfStop[stop] ){

                    if( !visitedRoutes.count( next_r ) ){

                        next_q.push( next_r );

                        visitedRoutes.insert( next_r );
                    }
                }
            }


            if( cur_q.empty() ){

                len++;
                swap( cur_q, next_q );

                while( !next_q.empty() )
                    next_q.pop();

            }

        }


        return -1;
    }
};












// class Solution {
// public:
//     int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {

//         if( source == target )
//             return 0;

//         unordered_map< int, vector<int> > routeOfStation;

//         unordered_map< int, unordered_set<int> > graph;

//         unordered_set<int> visitedRoute;

//         unordered_set<int> destinationRoute;

//         for( int i = 0 ; i < routes.size() ; i++ ){

//             for( auto station : routes[i] )
//                 routeOfStation[ station ].push_back( i );

//         }

//         for( auto& [ route, stations ] : routeOfStation ){

//             for( int i = 0 ; i < stations.size() ; i++ ){

//                 for( int j = i+1 ; j < stations.size() ; j++ ){

//                     graph[ stations[i] ].insert( stations[j] );
//                     graph[ stations[j] ].insert( stations[i] );

//                 }

//             }

//         }

//         for( auto route :routeOfStation[target] )
//             destinationRoute.insert( route );

//         int len = 1;

//         int curLayerSize = 0, nextLayerSize = 0;

//         queue< int > q;

//         for( auto route : routeOfStation[source] ){

//             q.push( route );

//             curLayerSize++;

//             visitedRoute.insert( route );

//         }

//         while( !q.empty() ){

//             for( int i = 0 ; i < curLayerSize ; i++ ){

//                 auto curRoute = q.front();

//                 if( destinationRoute.count( curRoute )  )
//                     return len;

//                 q.pop();

//                 for( auto nextRoute : graph[ curRoute ] ){

//                     if( !visitedRoute.count( nextRoute ) ){

//                         q.push( nextRoute );

//                         visitedRoute.insert ( nextRoute );

//                         nextLayerSize++;

//                     }
//                 }

//             }

//             swap( curLayerSize, nextLayerSize );

//             nextLayerSize = 0;

//             len++;

//         }

//         return -1;


        
//     }
// };
149471