We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->... forever.
We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.
Example:
Input: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation: 
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

 
Constraints:

1 <= routes.length <= 500.
1 <= routes[i].length <= 10^5.
0 <= routes[i][j] < 10 ^ 6.

Difficulty: interview

Starter code:

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:
        

Solutions:
["from collections import defaultdict\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        # sequence_to_route_id dict\n        # if when adding sequence ids to this dict, they are part of another route,\n        # merge them\n        max_int = 10**6\n        start_routes = set()\n        end_routes = set()\n        route_connections = defaultdict(lambda: set())\n        sequence_to_route_id_dict = {}\n        route_to_minbuscount = defaultdict(lambda: max_int)\n        for r_id, r in enumerate(routes):\n            for s in r:\n                if s == S:\n                    start_routes.add(r_id)\n                    route_to_minbuscount[r_id] = 1\n                if s == T:\n                    end_routes.add(r_id)\n                if s in sequence_to_route_id_dict:\n                    route_connections[r_id].add(sequence_to_route_id_dict[s])\n                    route_connections[sequence_to_route_id_dict[s]].add(r_id)\n                sequence_to_route_id_dict[s] = r_id\n        \n        # print(route_connections)\n        # print(start_routes)\n        # print(end_routes)\n        \n        current_route_buscount = [(s,1) for s in start_routes]\n        for r_id, buscount in current_route_buscount:\n            # print(current_route_buscount)\n            # print(dict(route_to_minbuscount))\n            for connection in route_connections[r_id]:\n                if route_to_minbuscount[connection] > buscount+1:\n                    route_to_minbuscount[connection] = buscount+1\n                    current_route_buscount.append((connection,buscount+1))\n        result = min(route_to_minbuscount[x] for x in end_routes)\n        return -1 if result == max_int else result\n\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        # You already at the terminal, so you needn't take any bus.\n        if S == T: return 0\n        \n        # You need to record all the buses you can take at each stop so that you can find out all\n        # of the stops you can reach when you take one time of bus.\n        # the key is stop and the value is all of the buses you can take at this stop.\n        stopBoard = {} \n        for bus, stops in enumerate(routes):\n            for stop in stops:\n                if stop not in stopBoard:\n                    stopBoard[stop] = [bus]\n                else:\n                    stopBoard[stop].append(bus)\n        \n        # The queue is to record all of the stops you can reach when you take one time of bus.\n        queue = deque([S])\n        # Using visited to record the buses that have been taken before, because you needn't to take them again.\n        visited = set()\n\n        res = 0\n        while queue:\n            # take one time of bus.\n            res += 1\n            # In order to traverse all of the stops you can reach for this time, you have to traverse\n            # all of the stops you can reach in last time.\n            pre_num_stops = len(queue)\n            for _ in range(pre_num_stops):\n                curStop = queue.popleft()\n                # Each stop you can take at least one bus, you need to traverse all of the buses at this stop\n                # in order to get all of the stops can be reach at this time.\n                for bus in stopBoard[curStop]:\n                    # if the bus you have taken before, you needn't take it again.\n                    if bus in visited: continue\n                    visited.add(bus)\n                    for stop in routes[bus]:\n                        if stop == T: return res\n                        queue.append(stop)\n        return -1\n        \n                \n", "from collections import defaultdict\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        to_routes = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                to_routes[j].add(i)\n        bfs = [(S, 0)]\n        seen = set([S])\n        for stop, bus in bfs:\n            if stop == T: return bus\n            for i in to_routes[stop]:\n                for j in routes[i]:\n                    if j not in seen:\n                        bfs.append((j, bus + 1))\n                        seen.add(j)\n                routes[i] = []  # seen route\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S==T: return 0\n        bus_dic = defaultdict(set)\n        for i, r in enumerate(routes):\n            for s in r:\n                bus_dic[s].add(i)\n\n        seen = {S}\n        av_bus = bus_dic[S]\n        for bus in bus_dic[S]:\n            if bus in bus_dic[T]:\n                return 1\n        cnt = 0\n        while av_bus:\n            tmp = set()\n            cnt += 1\n            for meh in range(len(av_bus)):\n                bus = av_bus.pop()\n                if bus in bus_dic[T]:\n                    return cnt\n                for s in routes[bus]:\n                    if s not in seen:\n                        seen.add(s)\n                        for bus in bus_dic[s]:\n                            if bus in bus_dic[T]:\n                                return cnt+1\n                            tmp.add(bus)\n            av_bus = tmp\n        return -1     ", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n\n        buses_from_stops = defaultdict(set)\n        for i, r in enumerate(routes) :\n            for v in r:\n                buses_from_stops[v].add(i)\n\n        memo = {}\n        def check(bus, hist):\n            if bus in memo:\n                return memo[bus]\n\n            if T in routes[bus]:\n                return 1\n            else:\n                v = 1000000\n                for stop in routes[bus]:\n                    for bs in buses_from_stops[stop]:\n                        if bs not in hist:\n                            nh = set(hist)\n                            nh.add(bs)\n                            v = min(v, check(bs, nh))\n                memo[bus] = v + 1\n                return v + 1\n\n        mn = 1000000\n        for bs in buses_from_stops[S]:\n                mn = min(mn, check(bs, set([bs])))\n        return mn if mn < 1000000 else -1", "class Solution:\n    def numBusesToDestination(self, routes, S, T):\n        if S == T: return 0\n        queue = collections.deque()\n        graph = collections.defaultdict(set)\n        routes = list(map(set, routes))\n        seen, targets = set(), set()\n        for i in range(len(routes)):\n            if S in routes[i]:  # possible starting route number\n                seen.add(i)\n                queue.append((i, 1))  # enqueue\n            if T in routes[i]:  # possible ending route number\n                targets.add(i)\n            for j in range(i+1, len(routes)):\n                if routes[j] & routes[i]:  # set intersection to check if route_i and route_j are connected\n                    graph[i].add(j)\n                    graph[j].add(i)\n        while queue:\n            cur, count = queue.popleft()\n            if cur in targets:\n                return count\n            for nei in graph[cur]:\n                if nei not in seen:\n                    queue.append((nei, count+1))\n                    seen.add(nei)\n        return -1", "from collections import defaultdict, deque\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S==T: return 0\n        bus2stops = defaultdict(list)\n        stop2buses = defaultdict(list)\n        for bus,stops in enumerate(routes):\n            for stop in stops:\n                bus2stops[bus].append(stop)\n                stop2buses[stop].append(bus)\n        \n        q = deque()\n        visitedBuses = set()\n        for bus in stop2buses[S]:\n            q.extend(bus2stops[bus])\n            visitedBuses.add(bus)\n        visitedStops = set(q)\n        if T in visitedStops: return 1\n        \n        numBuses = 2\n        while q:\n            for _ in range(len(q)):\n                currStop = q.popleft()\n\n                for bus in stop2buses[currStop]:\n                    if bus in visitedBuses: \n                        continue\n                    visitedBuses.add(bus)\n                    for stop in bus2stops[bus]:\n                        if stop not in visitedStops:\n                            if stop==T:\n                                return numBuses\n                            visitedStops.add(stop)\n                            q.append(stop)\n            numBuses+=1\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        toroute=collections.defaultdict(set)\n        seen={S}\n        for i, stops in enumerate(routes):\n            for j in stops:\n                toroute[j].add(i)\n                \n        \n        q=collections.deque([(S,0)])\n        while q:\n            s,b=q.popleft()\n            if s==T:\n                return b\n            for i in toroute[s]:\n                for j in routes[i]:\n                    if j not in seen:\n                        seen.add(s)\n                        q.append((j,b+1))\n                routes[i]=[]\n                \n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        res = 0\n        routeDones = set()\n        stations = {S}\n        while T not in stations:\n            newStations = set()\n            for i, route in enumerate(routes):\n                if i in routeDones or len(stations.intersection(set(route))) == 0:\n                    continue # case only continue?\n                newStations = newStations.union(set(route) - stations)\n                routeDones.add(i)\n            if len(newStations) == 0:\n                return -1\n            res +=1\n            stations=stations.union(newStations)\n\n        return res", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        routes, n = [set(r) for r in routes], len(routes)\n        g = [set() for _ in range(n)]\n        for i in range(n):\n            for j in range(i):\n                if set(routes[i]) & set(routes[j]): \n                    g[i].add(j), g[j].add(i)\n        seen, dst = set(i for i,r in enumerate(routes) if S in r), set(i for i,r in enumerate(routes) if T in r)\n        q = [(x, 1) for x in seen]\n        for x, d in q:\n            if x in dst: return d\n            for y in g[x]:\n                if y not in seen: seen.add(y), q.append((y, d+1))\n        return -1", "class Solution(object):\n    def numBusesToDestination(self, routes, S, T):\n        if S==T:\n            return 0\n        \n        queue = collections.deque()\n        graph = collections.defaultdict(set)\n        \n        routes = list(map(set,routes))\n        \n        seen, targets = set(),set()\n        \n        for i in range(len(routes)):\n            if S in routes[i]:\n                seen.add(i)\n                queue.append((i,1))\n            if T in routes[i]:\n                targets.add(i)\n            for j in range(i+1,len(routes)):\n                if routes[j] & routes[i]:\n                    graph[i].add(j)\n                    graph[j].add(i)\n   \n        while queue:\n            cur,count = queue.popleft()\n            if cur in targets:\n                return count\n            for nei in graph[cur]:\n                if nei not in seen:\n                    queue.append((nei,count+1))\n                    seen.add(nei)\n        return -1\n            \n                \n                    \n                \n                \n                \n            \n            \n        \n", "from collections import deque, defaultdict\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        route_dict = defaultdict(set)\n        for i, route in enumerate(routes):\n            for stop in route:\n                route_dict[stop].add(i)\n        \n        queue = deque([S])\n        seen = set([S])\n        buses = 0\n        while queue:\n            size = len(queue)\n            for _ in range(size):\n                stop = queue.popleft()\n                if stop == T:\n                    return buses\n                for i in route_dict[stop]:\n                    for j in routes[i]:\n                        if j not in seen:\n                            queue.append(j)\n                            seen.add(j)\n                    routes[i] = []\n            buses += 1\n        \n        return -1\n        \n                \n                \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        ans = 0\n        n = len(routes)\n        if S == T:\n            return 0\n        graph = collections.defaultdict(set)# stop -> bus #\n        queue = collections.deque()\n        visited_stop = set()\n        visited_bus = set()\n        for i in range(n):\n            for stop in routes[i]:\n                graph[stop].add(i)\n        print(graph)\n        queue.append(S)\n        visited_stop.add(S)\n        \n        while queue:\n            qLen = len(queue)\n            ans +=1\n            for i in range(qLen):\n                stop = queue.popleft()\n                for next_bus in graph[stop]:\n                    if next_bus in visited_bus:\n                        continue\n                    visited_bus.add(next_bus)\n                    for next_stop in routes[next_bus]:\n                        # if next_stop in visited_stop:\n                        #     continue\n                        if next_stop == T:\n                            print('here')\n                            return ans\n                        queue.append(next_stop)\n                        # visited_stop.add(next_stop)\n            print((queue, visited_stop, visited_bus))\n            \n            print(ans)\n        return -1 \n    \n# defaultdict(<class 'set'>, {1: {0}, 2: {0}, 7: {0, 1}, 3: {1}, 6: {1}})\n# deque([2]) {1, 2} {0}\n# deque([2, 7]) {1, 2, 7} {0}\n# 1\n# deque([3]) {1, 2, 3, 7} {0, 1}\n            \n\n           \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        \n        n = len(routes)\n        \n        graph = defaultdict(set)\n        \n        for i in range(n):\n            for j in range(i,n):\n                if set(routes[i]).intersection(routes[j]):\n                    graph[i].add(j)\n                    graph[j].add(i)\n                    \n        \n        # Get source and destination\n        for i in range(n):\n            if S in routes[i]:\n                if T in routes[i]:\n                    return 1  \n                source = i\n            elif T in routes[i]:\n                dest = i\n                \n                \n                \n        q = deque([[source, 1]])\n        visited = [False]*n\n        visited[source] = True\n        \n        while q:\n            node, dis = q.popleft()\n            if node == dest:\n                return dis\n            for u in graph[node]:\n                if not visited[u]:\n                    visited[u] = True\n                    q.append([u, dis +1])\n                    \n        return -1\n            \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        \n        graph   = collections.defaultdict(set)\n        \n        for bus, stops in enumerate(routes):\n            for stop in stops:\n                graph[stop].add(bus)\n        \n        queue   = collections.deque([S])\n        visited = set()\n        result  = int()\n        \n        while queue:\n            result  += 1\n            for _ in range(len(queue)):\n                currStop    = queue.popleft()\n                for bus in graph[currStop]:\n                    if bus not in visited:\n                        visited.add(bus)\n                        for stop in routes[bus]:\n                            if stop == T:\n                                return result\n                            queue.append(stop)\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        num_buses = len(routes)\n        bus_to_stop = defaultdict(set)\n        for bus, stops in enumerate(routes):\n            bus_to_stop[bus] = set(stops)\n        \n        def update_buses_used():\n            for bus in range(num_buses):\n                if bus in buses_used:\n                    continue\n                if stops_reached & bus_to_stop[bus]:\n                    buses_used.add(bus)\n        \n        def update_stops_reached(stops_reached):\n            for bus in buses_used:\n                stops_reached |= bus_to_stop[bus]\n        \n        buses_used = set()\n        stops_reached = {S}\n        pre_stop_count = 0\n        bus_count = 0\n        while len(stops_reached) > pre_stop_count:\n            if T in stops_reached:\n                return bus_count\n            pre_stop_count = len(stops_reached)\n            update_buses_used()\n            update_stops_reached(stops_reached)\n            bus_count += 1\n            \n        return -1\n        \n        \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        \n        n = len(routes)\n        \n        graph = defaultdict(set)\n        \n        for i in range(n):\n            for j in range(i+1,n):\n                if set(routes[i]).intersection(routes[j]):\n                    graph[i].add(j)\n                    graph[j].add(i)\n                    \n        \n        # Get source and destination\n        for i in range(n):\n            if S in routes[i]:\n                if T in routes[i]:\n                    return 1  \n                source = i\n            elif T in routes[i]:\n                dest = i\n                \n                \n                \n        q = deque([[source, 1]])\n        visited = [False]*n\n        visited[source] = True\n        \n        while q:\n            node, dis = q.popleft()\n            if node == dest:\n                return dis\n            for u in graph[node]:\n                if not visited[u]:\n                    visited[u] = True\n                    q.append([u, dis +1])\n                    \n        return -1\n            \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        queue = collections.deque()\n        routes = list(map(set, routes))\n        graph = collections.defaultdict(set)\n        visited, targets = set(), set()\n        for i in range(len(routes)):\n            if S in routes[i]:  # possible starting route number\n                visited.add(i)\n                queue.append((i, 1))  # enqueue\n            if T in routes[i]:  # possible ending route number\n                targets.add(i)\n            for j in range(i+1, len(routes)):\n                if routes[j] & routes[i]:  # set intersection to check if route_i and route_j are connected\n                    graph[i].add(j)\n                    graph[j].add(i)\n        while queue:\n            cur, depth = queue.popleft()\n            if cur in targets:\n                return depth\n            for nxt in graph[cur]:\n                if nxt not in visited:\n                    visited.add(nxt)\n                    queue.append((nxt, depth + 1))\n        return -1            ", "# Reference: https://leetcode.com/problems/bus-routes/discuss/122712/Simple-Java-Solution-using-BFS\nfrom collections import deque\nclass Solution:\n    def numBusesToDestination(self,routes, S, T):\n        if S == T: return 0\n        routes, n = [set(r) for r in routes], len(routes)\n        g = [set() for _ in range(n)]\n        for i in range(n):\n            for j in range(i):\n                if set(routes[i]) & set(routes[j]): \n                    g[i].add(j), g[j].add(i)\n        seen, dst = set(i for i,r in enumerate(routes) if S in r), set(i for i,r in enumerate(routes) if T in r)\n        q = [(x, 1) for x in seen]\n        for x, d in q:\n            if x in dst: return d\n            for y in g[x]:\n                if y not in seen: seen.add(y), q.append((y, d+1))\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        num_buses = len(routes)\n        bus_to_stop = defaultdict(set)\n        for bus, stops in enumerate(routes):\n            bus_to_stop[bus] = set(stops)\n        \n        def update_buses_used():\n            for bus in range(num_buses):\n                if bus in buses_used:\n                    continue\n                if stops_reached & bus_to_stop[bus]:\n                    buses_used.add(bus)\n        \n        def update_stops_reached():\n            for bus in buses_used:\n                stops_reached.update(bus_to_stop[bus])\n        \n        buses_used = set()\n        stops_reached = {S}\n        pre_stop_count = 0\n        bus_count = 0\n        while len(stops_reached) > pre_stop_count:\n            if T in stops_reached:\n                return bus_count\n            pre_stop_count = len(stops_reached)\n            update_buses_used()\n            update_stops_reached()\n            bus_count += 1\n            \n        return -1\n        \n        \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S==T: return 0\n        routes = [set(r) for r in routes]\n        \n        graph = collections.defaultdict(set)\n        for i in range(len(routes)):\n            for j in range(i+1,len(routes)):\n                if routes[i].intersection(routes[j]):\n                    graph[i].add(j)\n                    graph[j].add(i)\n                    \n        seen,end = set(),set()\n        for i,x in enumerate(routes):\n            if S in x: seen.add(i)\n            if T in x: end.add(i)\n        \n        q = [(n,1) for n in seen]\n        seen = set()\n        for n,d in q:\n            if n in end: return d\n            for x in graph[n]:\n                if x not in seen:\n                    seen.add(x)\n                    q.append((x,d+1))\n        return -1\n            \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S==T:\n            return 0\n        graph=collections.defaultdict(list)\n        for i,stops in enumerate(routes):\n            for s in stops:\n                graph[s].append(i)\n        que=graph[S]\n        visited=set()\n        steps=0\n        while que:\n            tmp=[]\n            for bus in que:\n                if bus in visited:\n                    continue\n                visited.add(bus)\n                for stop in routes[bus]:\n                    if stop==T:\n                        return steps+1\n                    for bus2 in graph[stop]:\n                        if bus2 not in visited:\n                            tmp.append(bus2)\n                            \n            que=tmp\n            steps+=1\n        return -1\n#         if S == T: return 0\n#         routes = list(map(set, routes))\n#         graph = collections.defaultdict(set)\n#         for i, r1 in enumerate(routes):\n#             for j in range(i+1, len(routes)):\n#                 r2 = routes[j]\n#                 if any(r in r2 for r in r1):\n#                     graph[i].add(j)\n#                     graph[j].add(i)\n\n#         seen, targets = set(), set()\n#         for node, route in enumerate(routes):\n#             if S in route: seen.add(node)\n#             if T in route: targets.add(node)\n\n#         queue = [(node, 1) for node in seen]\n#         for node, depth in queue:\n#             if node in targets: return depth\n#             for nei in graph[node]:\n#                 if nei not in seen:\n#                     seen.add(nei)\n#                     queue.append((nei, depth+1))\n#         return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        dic_stops = collections.defaultdict(set)\n        for i, stops in enumerate(routes):\n            for s in stops:\n                dic_stops[s].add(i)\n        visited_stops = set([S])\n        visited_buses = set()\n        queue = collections.deque([(S, 1)])\n        while queue:\n            stop, cnt = queue.popleft()\n            for bus in dic_stops[stop]:\n                if bus not in visited_buses:\n                    visited_buses.add(bus)\n                    for s in routes[bus]:\n                        if s not in visited_stops:\n                            if s == T: return cnt\n                            visited_stops.add(s)\n                            queue.append((s, cnt + 1))\n        return -1\n                    \n        \n                            \n                \n                \n", "from collections import deque\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        # graph of bus stop to busses (which busses stop at that stop)\n        graph = {}\n        for bus in range(len(routes)):\n            route = routes[bus]\n            for stop in route:\n                if stop in graph:\n                    graph[stop].append(bus)\n                else:\n                    graph[stop] = [bus]\n        \n        # tuple for bus num and number of busses taken\n        q = deque()\n        q.append((-1, 0))\n        taken = set()\n        \n        while len(q) > 0:\n            busTuple = q.popleft()\n            bus = busTuple[0]\n            numBusses = busTuple[1]\n            \n            if bus != -1 and T in routes[bus]:\n                return numBusses\n            \n            if bus == -1:\n                for nextBus in graph[S]:\n                    if nextBus not in taken:\n                        taken.add(nextBus)\n                        q.append((nextBus, numBusses + 1))\n            else:\n                for stop in routes[bus]:\n                    for nextBus in graph[stop]:\n                        if nextBus not in taken:\n                            taken.add(nextBus)\n                            q.append((nextBus, numBusses + 1))\n        return -1\n            \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S==T:\n            return 0\n        graph=collections.defaultdict(list)\n        for i,stops in enumerate(routes):\n            for s in stops:\n                graph[s].append(i)\n        que=graph[S]\n        visited=set()\n        steps=0\n        while que:\n            tmp=[]\n            for bus in que:\n                if bus in visited:\n                    continue\n                visited.add(bus)\n                for stop in routes[bus]:\n                    if stop==T:\n                        return steps+1\n                    for bus2 in graph[stop]:\n                        if bus2 not in visited:\n                            tmp.append(bus2)\n            que=tmp\n            steps+=1\n        return -1\n", "from queue import Queue\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n\n        stopToBus = {}\n        for bus in range(len(routes)):\n            for stop in routes[bus]:\n                stopToBus.setdefault(stop, [])\n                stopToBus[stop].append(bus)\n        \n        q = Queue(maxsize=1000000)\n        busVis = [False] * len(routes)\n        stopVis = [False] * 1000000\n        q.put((S, 0))\n        while q.qsize() > 0:\n            stop, dist = q.get()\n            stopVis[stop] = True\n            for bus in stopToBus[stop]:\n                if busVis[bus] == False:\n                    busVis[bus] = True\n                    for ds in routes[bus]:\n                        if stopVis[ds] == False:\n                            if ds == T:\n                                return dist + 1\n\n                            q.put((ds, dist + 1))\n        \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        \n        if S == T:\n            return 0\n        \n        graph = collections.defaultdict(list)\n        \n        #capture the bus routes\n        for index, route in enumerate(routes):\n            for stop in route:\n                \n                graph[stop].append(index)\n                \n        print(graph)        \n        queue = graph[S]\n        visited = set()\n        steps = 0\n        \n        while queue:\n            temp = []\n            #check each bus of the soure node\n            for bus in queue:\n                if bus in visited:\n                    continue\n                else:    \n                    visited.add(bus)\n                    #check the  stops of each bus\n                    for stops in routes[bus]:\n                        if stops == T:\n                            return steps + 1\n                         #check the bus of each stops\n                        for buses in graph[stops]:\n                            if buses not in visited:\n                                #each and every level fill it with new buses\n                               temp.append(buses)\n                        \n            queue = temp            \n            steps += 1\n            \n            \n        return -1 \n        \n   \n        \n        \n#         if S==T:\n#             return 0\n#         graph=collections.defaultdict(list)\n#         for i,stops in enumerate(routes):\n#             for s in stops:\n#                 graph[s].append(i)\n#         que=graph[S]\n#         visited=set()\n#         steps=0\n#         while que:\n#             tmp=[]\n#             for bus in que:\n#                 if bus in visited:\n#                     continue\n#                 visited.add(bus)\n#                 for stop in routes[bus]:\n#                     if stop==T:\n#                         return steps+1\n#                     for bus2 in graph[stop]:\n#                         if bus2 not in visited:\n#                             tmp.append(bus2)\n                            \n#             que=tmp\n#             steps+=1\n#         return -1\n#         if S == T: return 0\n#         routes = list(map(set, routes))\n#         graph = collections.defaultdict(set)\n#         for i, r1 in enumerate(routes):\n#             for j in range(i+1, len(routes)):\n#                 r2 = routes[j]\n#                 if any(r in r2 for r in r1):\n#                     graph[i].add(j)\n#                     graph[j].add(i)\n\n#         seen, targets = set(), set()\n#         for node, route in enumerate(routes):\n#             if S in route: seen.add(node)\n#             if T in route: targets.add(node)\n\n#         queue = [(node, 1) for node in seen]\n#         for node, depth in queue:\n#             if node in targets: return depth\n#             for nei in graph[node]:\n#                 if nei not in seen:\n#                     seen.add(nei)\n#                     queue.append((nei, depth+1))\n#         return -1\n", "class Solution:\n    # O(n_stops x n_buses) time, O(n_stops x n_buses) space\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        num_buses = len(routes)\n        bus_to_stop = defaultdict(set)\n        for bus, stops in enumerate(routes):\n            bus_to_stop[bus] = set(stops)\n        \n        def update_buses_used():\n            for bus in range(num_buses):\n                if bus in buses_used:\n                    continue\n                if stops_reached & bus_to_stop[bus]:\n                    buses_used.add(bus)\n        \n        def update_stops_reached():\n            for bus in buses_used:\n                stops_reached.update(bus_to_stop[bus])\n        \n        buses_used = set()\n        stops_reached = {S}\n        pre_stop_count = 0\n        bus_count = 0\n        while len(stops_reached) > pre_stop_count:\n            if T in stops_reached:\n                return bus_count\n            pre_stop_count = len(stops_reached)\n            update_buses_used()\n            update_stops_reached()\n            bus_count += 1\n            \n        return -1\n\n        \n        \n        \n", "class Solution(object):\n    def numBusesToDestination(self, routes, S, T):\n        if S == T: return 0\n        routes = list(map(set, routes))\n        graph = collections.defaultdict(set)\n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                for r in r1:\n                    if r in r2:\n                        graph[i].add(j)\n                        graph[j].add(i)\n\n        seen, targets = set(), set()\n        for node, route in enumerate(routes):\n            if S in route: seen.add(node)\n            if T in route: targets.add(node)\n\n        queue = [(node, 1) for node in seen]\n        for node, depth in queue:\n            if node in targets: return depth\n            for nei in graph[node]:\n                if nei not in seen:\n                    seen.add(nei)\n                    queue.append((nei, depth+1))\n        return -1", "from collections import defaultdict\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if(S==T):\n            return 0\n        routes = [set(r) for r in routes]\n        graph = defaultdict(list)\n        for i in range(len(routes)):\n            for j in range(i+1, len(routes)):\n                for k in routes[i]:\n                    if k in routes[j]:\n                        graph[j].append(i)\n                        graph[i].append(j)\n                        break\n        queue = []\n        for i, poss in enumerate(routes):\n            if(S in poss):\n                queue.append((i, 1))\n        seen = set()\n        while(queue):\n            cur, cost = queue.pop(0)\n            if(T in routes[cur]):\n                return cost\n            seen.add(cur)\n            for child in graph[cur]:\n                if(child not in seen):\n                    queue.append((child, cost+1))\n        return -1", "from collections import defaultdict\nfrom collections import deque\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        '''\n        node1 => {1,2,7}\n        1 => node1\n        3 => node2\n        2 => node1\n        6 => node2\n        7 => node1, node2\n        \n        node2 => {3,6,7}\n        '''\n        buses = defaultdict(list) ## map stops to buses\n        for i in range(len(routes)):\n            for stop in routes[i]:\n                buses[stop].append(i)\n                \n        queue = deque([(S,0)])\n        busVisited = set()\n        while queue:\n            stop, busCnt = queue.popleft()\n            if stop == T:\n                return busCnt\n            for bus in buses[stop]:\n                if bus in busVisited:\n                    continue\n                busVisited.add(bus)\n                for reachableStop in routes[bus]:\n                    #if reachableStop not in visited:\n                    queue.append((reachableStop, busCnt+1))\n            \n        return -1   \n            \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        # if S==T: return 0\n        # g = defaultdict(list)\n        # q = []\n        # t = set()\n        # routes = list(map(set, routes))\n        # for i, r1 in enumerate(routes):\n        #     if S in r1: q.append((i, 1))\n        #     if T in r1: t.add(i)\n        #     for j in range(i+1, len(routes)):\n        #         r2 = routes[j]\n        #         if any(s in r2 for s in r1):\n        #             g[i].append(j)\n        #             g[j].append(i)\n        # seen = set(q)\n        # while q:\n        #     node, jumps = q.pop(0)\n        #     if node in t: return jumps\n        #     for nxt in g[node]:\n        #         if nxt not in seen:\n        #             seen.add(nxt)\n        #             q.append((nxt, jumps+1))\n        # return -1\n        \n#         st = defaultdict(set)\n#         rt = defaultdict(set)\n#         for i, route in enumerate(routes):\n#             for stop in route:\n#                 st[stop].add(i)\n#                 rt[i].add(stop)\n        \n#         q = deque([(S,0)])\n#         st_seen = set()\n#         rt_seen = set()\n#         while q:\n#             node, jumps = q.popleft()\n#             if node == T: return jumps\n#             for r in st[node]:\n#                 if r not in rt_seen:\n#                     rt_seen.add(r)\n#                     for stop in routes[r]:\n#                         if stop not in st_seen:\n#                             q.append((stop, jumps+1))\n#                             st_seen.add(stop)\n#         return -1\n    \n    \n        to_routes = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                to_routes[j].add(i)\n        bfs = [(S, 0)]\n        seen = set([S])\n        for stop, bus in bfs:\n            if stop == T: return bus\n            for i in to_routes[stop]:\n                for j in routes[i]:\n                    if j not in seen:\n                        bfs.append((j, bus + 1))\n                        seen.add(j)\n                routes[i] = []  # seen route\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        num_buses = len(routes)\n        bus_to_stop = defaultdict(set)\n        stop_to_bus = defaultdict(set)\n        for bus, stops in enumerate(routes):\n            bus_to_stop[bus] = set(stops)\n            for stop in stops:\n                stop_to_bus[stop].add(bus)\n        \n        \n        def update_buses_used():\n            for bus in range(num_buses):\n                if bus in buses_used:\n                    continue\n                if stops_reached & bus_to_stop[bus]:\n                    buses_used.add(bus)\n        \n        def update_stops_reached(stops_reached):\n            for bus in buses_used:\n                stops_reached |= bus_to_stop[bus]\n        \n        buses_used = set()\n        stops_reached = {S}\n        pre_stop_count = 0\n        bus_count = 0\n        while len(stops_reached) > pre_stop_count:\n            if T in stops_reached:\n                return bus_count\n            pre_stop_count = len(stops_reached)\n            update_buses_used()\n            update_stops_reached(stops_reached)\n            bus_count += 1\n            \n        return -1\n        \n        \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        queue = collections.deque()\n        dic_buses = collections.defaultdict(set)\n        dic_stops = collections.defaultdict(set)\n        visited = set()\n        reachable = set()\n        for i, stops in enumerate(routes):\n            dic_buses[i] = set(stops)\n            if S in dic_buses[i]:\n                if T in dic_buses[i]: return 1\n                visited.add(i)\n                reachable |= dic_buses[i]\n                queue.append(i)\n            for j in dic_buses[i]:\n                dic_stops[j].add(i)\n        bus_need = 2\n        visited_stops = set()\n        while queue:\n            length = len(queue)\n            for _ in range(length):\n                bus = queue.popleft()\n                for stop in dic_buses[bus]:\n                    if stop in visited_stops: continue\n                    visited_stops.add(stop)\n                    for b in dic_stops[stop]:\n                        if b not in visited:\n                            if T in dic_buses[b]:\n                                return bus_need\n                            queue.append(b)\n            bus_need += 1\n        return -1\n                            \n                \n                \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        N = len(routes)\n        if S == T:\n            return 0\n        routes = list(map(set, routes))\n        g = [set() for _ in range(N)]\n        for ii, r1 in enumerate(routes):\n            for jj in range(ii + 1, N):\n                r2 = routes[jj]\n                if any([1 for kk in r2 if kk in r1]):\n                    g[ii].add(jj)\n                    g[jj].add(ii)\n        ss, tt = set(), set()\n        for ii, jj in enumerate(routes):\n            if S in jj:\n                ss.add(ii)\n            if T in jj:\n                tt.add(ii)\n        queue = [(ii, 1) for ii in ss]\n        for ii, jj in queue:\n            if ii in tt:\n                return jj\n            for kk in g[ii]:\n                if kk not in ss:\n                    ss.add(kk)\n                    queue.append((kk, jj + 1))\n        return -1\n", "from collections import defaultdict\nfrom collections import deque\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        '''\n        node1 => {1,2,7}\n        1 => node1\n        3 => node2\n        2 => node1\n        6 => node2\n        7 => node1, node2\n        \n        node2 => {3,6,7}\n        '''\n        buses = defaultdict(list) ## map stops to buses\n        for i in range(len(routes)):\n            for stop in routes[i]:\n                buses[stop].append(i)\n                \n        queue = deque([(S,0)])\n        visited = set()\n        busVisited = set()\n        while queue:\n            stop, busCnt = queue.popleft()\n            visited.add(stop)\n            if stop == T:\n                return busCnt\n            for bus in buses[stop]:\n                if bus in busVisited:\n                    continue\n                busVisited.add(bus)\n                for reachableStop in routes[bus]:\n                    if reachableStop not in visited:\n                        queue.append((reachableStop, busCnt+1))\n            \n        return -1   \n            \n", "from collections import defaultdict, deque\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        path = defaultdict(list)\n        for i, v in enumerate(routes):\n            for bus_stop in v:\n                path[bus_stop].append(i)\n        used = set()\n        bus_seen = set([S])\n        queue = deque([S])\n        taken = 0\n        while queue:\n            for _ in range(len(queue)):\n                bus_stop = queue.popleft()\n                if bus_stop == T:\n                    return taken\n                for route in path[bus_stop]:\n                    if route not in used:\n                        used.add(route)\n                        for next_bus in routes[route]:\n                            if next_bus not in bus_seen:\n                                queue.append(next_bus)\n            taken += 1\n        return -1\n                  \n                        \n        \n                \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S== T:\n            return 0\n        graph = collections.defaultdict(list)\n        for i,j in enumerate(routes):\n            for stops in j:\n                graph[stops].append(i)\n                \n        q = collections.deque(graph[S])\n        visited = set()\n        steps = 0\n        while q:\n            temp =[]\n            \n            for bus in q:\n                if bus in visited:\n                    continue\n                visited.add(bus)\n                for r in routes[bus]:\n                    if r==T:\n                        return steps + 1\n                    for b in graph[r]:\n                        if b not in visited:\n                            temp.append(b)\n            q = temp\n            steps+= 1\n        return -1\n                \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S==T:\n            return 0\n        stops = collections.defaultdict(list)\n        for i, route in enumerate(routes):\n            for stop in route:\n                stops[stop].append(i)\n        num_routes = len(routes)\n        expanded = set()\n        q = collections.deque()\n        routes = [set(route) for route in routes]\n        for route in stops[S]:\n            q.append([route,1])\n            expanded.add(route)\n        while q:\n            cur_route, buses_taken = q.popleft()\n            if T in routes[cur_route]:\n                return buses_taken\n            for stop in routes[cur_route]:\n                for transfer_route in stops[stop]:\n                    if transfer_route not in expanded:\n                        expanded.add(transfer_route)\n                        q.append([transfer_route,buses_taken+1])\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        stop = {}\n        for i in range(len(routes)):\n            for s in routes[i]:\n                if s not in stop:\n                    stop[s] = set()\n                stop[s].add(i)\n        stack = [(S, 0)]\n        visited = set([S])\n        while stack:\n            node, level = stack.pop(0)\n            for bus in stop[node]:\n                for s in set(routes[bus]) - visited:\n                    if s == T:\n                        return level + 1\n                    stack.append((s, level + 1))\n                    visited.add(s)\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        \n        graph = defaultdict(list)\n        \n        start = []\n        end = set()\n        for i in range(len(routes)):\n            iset = set(routes[i])\n            for j in range(i+1, len(routes)):\n                if any(r in iset for r in routes[j]):\n                    graph[i].append(j)\n                    graph[j].append(i)\n                    \n            if S in iset:\n                start.append(i)\n            if T in iset:\n                end.add(i)\n                \n        qu = deque(start)\n        \n        ret = 1\n        visited = set()\n        while qu:\n            nextqu = deque()\n            while qu:\n                cur = qu.pop()\n                \n                if cur in end: return ret\n                \n                if cur in visited: continue\n                visited.add(cur)\n                \n                for n in graph[cur]:\n                    if n not in visited:\n                        nextqu.append(n)\n                        \n            qu = nextqu\n            ret += 1\n        \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        stop_to_bus = collections.defaultdict(list)\n        for bus,stops in enumerate(routes):\n            for stop in stops:\n                stop_to_bus[stop].append(bus)\n        \n        q = collections.deque([S])\n        seen_bus = set()\n        # seen_stop = set()\n        step = -1\n        while q:\n            step += 1\n            for _ in range(len(q)):\n                stop = q.popleft()\n                if stop == T:\n                    return step\n                for bus in stop_to_bus[stop]:\n                    if bus in seen_bus:\n                        continue\n                    seen_bus.add(bus)\n                    for next_stop in routes[bus]:\n                        # if next_stop in seen_stop:\n                        #     continue\n                        q.append(next_stop)\n                        # seen_stop.add(stop)\n        return -1        ", "class Solution(object):\n    def numBusesToDestination(self, routes, S, T):\n        if S == T:\n            return 0\n        \n        to_routes = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                to_routes[j].add(i)\n        bfs = [(S, 0)]\n        # seen = set([S])\n        for stop, bus in bfs:\n            for i in to_routes[stop]:\n                for j in routes[i]:\n                    # if j not in seen:\n                    if j == T: \n                        return bus + 1\n                    bfs.append((j, bus + 1))\n                        # seen.add(j)\n                routes[i] = []  # seen route\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n#         if S==T:\n#             return 0\n#         graph=collections.defaultdict(list)\n#         for i,stops in enumerate(routes):\n#             for s in stops:\n#                 graph[s].append(i)\n#         que=graph[S]\n#         visited=set()\n#         steps=0\n#         while que:\n#             tmp=[]\n#             for bus in que:\n#                 if bus in visited:\n#                     continue\n#                 visited.add(bus)\n#                 for stop in routes[bus]:\n#                     if stop==T:\n#                         return steps+1\n#                     for bus2 in graph[stop]:\n#                         if bus2 not in visited:\n#                             tmp.append(bus2)\n#             que=tmp\n#             steps+=1\n#         return -1\n        if S == T: return 0\n        routes = list(map(set, routes))\n        graph = collections.defaultdict(set)\n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n\n        seen, targets = set(), set()\n        for node, route in enumerate(routes):\n            if S in route: seen.add(node)\n            if T in route: targets.add(node)\n\n        queue = [(node, 1) for node in seen]\n        for node, depth in queue:\n            if node in targets: return depth\n            for nei in graph[node]:\n                if nei not in seen:\n                    seen.add(nei)\n                    queue.append((nei, depth+1))\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        graph = collections.defaultdict(list)\n        for i,stops in enumerate(routes):\n            for stop in stops:\n                graph[stop].append(i)\n                \n        q = graph[S]\n        visited = set()\n        steps = 0\n        while q:\n            tmp = []\n            for bus in q:\n                if bus in visited:\n                    continue\n                visited.add(bus)\n                for stop in routes[bus]:\n                    if stop == T:\n                        return steps + 1\n                    for bus2 in graph[stop]:\n                        if bus2 not in visited:\n                            tmp.append(bus2)\n                            \n            q = tmp\n            steps += 1\n        return -1", "from collections import defaultdict, deque\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        path = defaultdict(list)\n        for i, v in enumerate(routes):\n            for bus_stop in v:\n                path[bus_stop].append(i)\n        used = set()\n        queue = deque([S])\n        taken = 0\n        while queue:\n            for _ in range(len(queue)):\n                bus_stop = queue.popleft()\n                if bus_stop == T:\n                    return taken\n                for route in path[bus_stop]:\n                    if route not in used:\n                        used.add(route)\n                        for next_bus in routes[route]:\n                            if next_bus != bus_stop:\n                                queue.append(next_bus)\n            taken += 1\n        return -1\n                  \n                        \n        \n                \n", "from collections import defaultdict, deque\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        R = defaultdict(list)\n        \n        for idx, r in enumerate(routes):\n            for s in r:\n                R[s].append(idx)\n        \n        \n        queue = deque([(S, 0)])\n        visited = set()\n        \n        while queue:\n            cur, res = queue.popleft()\n            if cur == T:\n                return res\n            \n            for stop in R[cur]:\n                if stop not in visited:\n                    visited.add(stop)\n                    for nxt in routes[stop]:\n                        if nxt != cur:\n                            queue.append((nxt, res + 1))\n        return -1\n                            \n            \n            \n", "from collections import defaultdict, deque\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        d = defaultdict(list)\n        visited = set()\n        for idx, r in enumerate(routes):\n            for s in r:\n                d[s].append(idx)\n        \n        queue = deque([(S, 0)])\n        while queue:\n            cur, step = queue.popleft()\n            \n            if cur == T:\n                return step\n            \n            for r in d[cur]:\n                if r not in visited:\n                    for s in routes[r]:\n                        queue.append((s, step+1))\n                    visited.add(r)\n        \n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        routes = list(map(set, routes))\n        graph = collections.defaultdict(set)\n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n\n        seen, targets = set(), set()\n        for node, route in enumerate(routes):\n            if S in route: seen.add(node)\n            if T in route: targets.add(node)\n\n        queue = [(node, 1) for node in seen]\n        for node, depth in queue:\n            if node in targets: return depth\n            for nei in graph[node]:\n                if nei not in seen:\n                    seen.add(nei)\n                    queue.append((nei, depth+1))\n        return -1", "class Solution(object):\n    def numBusesToDestination(self, routes, S, T):\n        if S == T: return 0\n        routes = list(map(set, routes))\n        graph = collections.defaultdict(set)\n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n\n        seen, targets = set(), set()\n        for node, route in enumerate(routes):\n            if S in route: seen.add(node)\n            if T in route: targets.add(node)\n\n        queue = [(node, 1) for node in seen]\n        for node, depth in queue:\n            if node in targets: return depth\n            for nei in graph[node]:\n                if nei not in seen:\n                    seen.add(nei)\n                    queue.append((nei, depth+1))\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S==T: return 0\n        g = defaultdict(list)\n        q = []\n        t = set()\n        routes = list(map(set, routes))\n        for i, r1 in enumerate(routes):\n            if S in r1: q.append((i, 1))\n            if T in r1: t.add(i)\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                if any(s in r2 for s in r1):\n                    g[i].append(j)\n                    g[j].append(i)\n        seen = set(q)\n        while q:\n            node, jumps = q.pop(0)\n            if node in t: return jumps\n            for nxt in g[node]:\n                if nxt not in seen:\n                    seen.add(nxt)\n                    q.append((nxt, jumps+1))\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        routes = list(map(set, routes))\n        graph = collections.defaultdict(set)\n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n        \n        visited, targets = set(), set()\n        for bus, route in enumerate(routes): \n            if S in route: \n                visited.add(bus)\n            if T in route: \n                targets.add(bus)\n        \n        queue = []\n        for bus in visited: \n            queue.append((bus, 1))\n        while queue: \n            bus, numBuses = queue.pop(0)\n            if bus in targets: \n                return numBuses\n            visited.add(bus)\n            for connecting_bus in graph[bus]: \n                if connecting_bus not in visited: \n                    queue.append((connecting_bus, numBuses+1))\n        return -1", "from collections import defaultdict\nclass Solution():\n    def numBusesToDestination(self, routes, S, T):\n        if S == T: return 0\n        routes = list(map(set, routes))\n        graph = defaultdict(set)\n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n\n        seen, targets = set(), set()\n        for node, route in enumerate(routes):\n            if S in route: seen.add(node)\n            if T in route: targets.add(node)\n\n        queue = [(node, 1) for node in seen]\n        for node, depth in queue:\n            if node in targets: return depth\n            for nei in graph[node]:\n                if nei not in seen:\n                    seen.add(nei)\n                    queue.append((nei, depth+1))\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        to_routes = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                to_routes[j].add(i)\n        bfs = [(S, 0)]\n        seen = set([S])\n        for stop, bus in bfs:\n            if stop == T: return bus\n            for i in to_routes[stop]:\n                for j in routes[i]:\n                    if j not in seen:\n                        bfs.append((j, bus + 1))\n                        seen.add(j)\n                routes[i] = []  # seen route\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int):\n        \n        graph = collections.defaultdict(list)\n        for i in range(len(routes)):\n            for route in routes[i]:\n                graph[route].append(i)\n        \n        q = collections.deque([(S, 0)])\n        visited = set()\n        \n        while q:\n        \n            cur_stop, out = q.popleft()    \n            if cur_stop == T: \n                return out\n            for bus in graph[cur_stop]:\n                if bus not in visited:\n                    visited.add(bus)\n                    for stop in routes[bus]:\n                        q.append((stop, out + 1))\n        return -1", "from collections import defaultdict, deque\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        routes = [set(route) for route in routes]\n        graph = collections.defaultdict(set)\n        for i, r1 in enumerate(routes):\n            for j in range(i+1,len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n        seen = set()\n        target = set()\n        for node,route in enumerate(routes):\n            if S in route: \n                seen.add(node)\n            if T in route: \n                target.add(node)\n        q = deque()\n        for node in seen:\n            q.append((node,1))\n        while q:\n            curr, depth = q.popleft()\n            if curr in target:\n                return depth\n            for child in graph[curr]:\n                if child not in seen:\n                    seen.add(child)\n                    q.append((child,depth+1))\n        return -1\n        \n        \n        \n                \n", "class Solution:\n    def numBusesToDestination(self, routes, S, T):\n        if S == T: return 0\n        routes = list(map(set, routes))\n        graph = collections.defaultdict(set)\n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n\n        seen, targets = set(), set()\n        for node, route in enumerate(routes):\n            if S in route: seen.add(node)\n            if T in route: targets.add(node)\n\n        queue = [(node, 1) for node in seen]\n        for node, depth in queue:\n            if node in targets: return depth\n            for nei in graph[node]:\n                if nei not in seen:\n                    seen.add(nei)\n                    queue.append((nei, depth+1))\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        graph = collections.defaultdict(set) # node is the bus, not stop\n        routes = list(map(set, routes))\n        for i, r1 in enumerate(routes):\n            for j in range(i + 1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n        \n        visited, targets = set(), set()\n        for i, r in enumerate(routes):\n            if S in r:\n                visited.add(i)\n            if T in r:\n                targets.add(i)\n        \n        queue = collections.deque([(node, 1) for node in visited])\n        while queue:\n            node, step = queue.popleft()\n            if node in targets:\n                return step\n            for neighbor in graph[node]:\n                if neighbor not in visited:\n                    visited.add(neighbor)\n                    queue.append((neighbor, step + 1))\n        return -1\n            \n        \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n# # \u4ee5\u7ad9\u70b9\u4f5c\u4e3anode\u5efa\u7acbgraph\uff0c\u7ad9\u70b9\u76f4\u63a5\u7d22\u5f15\u4e0b\u4e00\u4e2a\u7ad9\u70b9: time limit exceeded... \u6000\u7591\u662f\u6784\u5efagraph\u592a\u8017\u65f6\n#         stop_graph = {}\n#         visited = set()\n#         for rt in routes:\n#             for i in range(len(rt)):\n#                 if rt[i] not in stop_graph: stop_graph[rt[i]] = set(rt[:i] + rt[i+1:])\n#                 else: \n#                     # print(rt[i], set(rt[:i] + rt[i+1:]))\n#                     stop_graph[rt[i]] = stop_graph[rt[i]].union(set(rt[:i] + rt[i+1:]))\n#         #BFS\n#         # visited = set()\n#         # print(stop_graph)\n#         if S == T: return 0\n#         if S not in stop_graph or T not in stop_graph: return -1\n#         cnt = 0\n#         queue = [S]\n#         visited = set(queue)\n#         while queue:\n#             # print(queue)\n#             size = len(queue)\n#             for _ in range(size):\n#                 curr_stop = queue.pop(0)\n#                 for next_stop in stop_graph[curr_stop]:\n#                     if next_stop in visited: continue\n#                     if next_stop == T: return cnt + 1\n#                     queue.append(next_stop) \n#                     visited.add(next_stop)\n#             cnt += 1\n#         else: return -1\n\n# \u4ee5\u7ad9\u70b9\u4f5c\u4e3anode\u5efa\u7acbgraph\uff0c\u4f46\u7528\u7ad9\u70b9\u7d22\u5f15bus\u73ed\u6b21\uff0c\u518d\u7528Bus\u7d22\u5f15\u7ad9\u70b9\u7684\u5f62\u5f0f\n# \uff01\uff01\uff01\u907f\u514dtime limit exceed\u65b9\u6cd5\u5fc5\u505a\u4e8b\u9879\uff1a\u8bbe\u4e24\u4e2aset()\u5206\u522b\u8bb0\u5f55\u904d\u5386\u8fc7\u7684bust stop & bus route\uff0c\u6bcf\u4e2astop / route\u90fd\u53ea\u5e94\u8be5\u6700\u591a\u5750\u4e00\u6b21\uff0c\u8fd9\u6837\u80fd\u907f\u514d\u91cd\u590d\u4fbf\u5229stop/route\u5e26\u6765\u7684for\u5faa\u73af\u8017\u65f6\u6700\u7ec8\u5bfc\u81f4\u65f6\u95f4\u6ea2\u51fa\n        graph = {}\n        for i in range(len(routes)):\n            for st in routes[i]:\n                if st not in graph: graph[st] = [i]\n                else: graph[st].append(i)\n        \n        visited_st = set([S])\n        if S == T: return 0\n        if S not in graph or T not in graph: return -1\n        queue = graph[S]\n        # print(graph[S])\n        visited_rt = set(graph[S])\n        cnt = 0\n        while queue:\n            cnt += 1\n            size = len(queue)\n            for _ in range(size):\n                curr_rt_ind = queue.pop(0)\n                # if curr_rt_ind in visited: continue\n                # visited.add(curr_rt_ind)\n                for st in routes[curr_rt_ind]:\n                    if st in visited_st: continue\n                    if st == T: return cnt\n                    visited_st.add(st)\n                    for rt_ind in graph[st]:\n                        if rt_ind in visited_rt: continue\n                        queue.append(rt_ind)\n                        visited_rt.add(rt_ind)\n        else: return -1\n\n#         if S == T: return 0\n#         # routes = set(routes)\n#         graph = collections.defaultdict(set)\n#         for i, r1 in enumerate(routes):\n#             for j in range(i+1, len(routes)):\n#                 r2 = routes[j]\n#                 if any(r in r2 for r in r1):\n#                     graph[i].add(j)\n#                     graph[j].add(i)\n\n#         seen, targets = set(), set()\n#         for node, route in enumerate(routes):\n#             if S in route: seen.add(node)\n#             if T in route: targets.add(node)\n\n#         queue = [(node, 1) for node in seen]\n#         for node, depth in queue:\n#             if node in targets: return depth\n#             for nei in graph[node]:\n#                 if nei not in seen:\n#                     seen.add(nei)\n#                     queue.append((nei, depth+1))\n#         return -1\n            \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        graph = collections.defaultdict(set)\n        routes = list(map(set, routes))\n        for i, r1 in enumerate(routes):\n            for j in range(i + 1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n        \n        visited, targets = set(), set()\n        for i, r in enumerate(routes):\n            if S in r:\n                visited.add(i)\n            if T in r:\n                targets.add(i)\n        \n        queue = collections.deque([(node, 1) for node in visited])\n        while queue:\n            node, step = queue.popleft()\n            if node in targets:\n                return step\n            for neighbor in graph[node]:\n                if neighbor not in visited:\n                    visited.add(neighbor)\n                    queue.append((neighbor, step + 1))\n        return -1\n            \n        \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        import queue\n        \n        if S == T:\n            return 0\n        #turn routes into graph\n        edge_dict = {}\n        for i in range(len(routes)):\n            for j in range(i+1, len(routes)):\n                if i not in edge_dict:\n                    edge_dict[i] = {}\n                    \n                if j not in edge_dict:\n                    edge_dict[j] = {}\n            \n                if len(set(routes[i]).intersection(set(routes[j]))) != 0:\n                    edge_dict[i][j] = 1\n                    edge_dict[j][i] = 1    \n            \n        #print(edge_dict)    \n        #bfs on this graph, starting at S trying to get to T\n        frontier = queue.SimpleQueue()\n        seen = {}\n    \n\n        for i in range(len(routes)):\n            if S in routes[i]:\n                frontier.put((i, 1))\n                seen[i] = 1\n        \n        while not frontier.empty():\n            node, dist = frontier.get()\n            #print(node)\n            if T in routes[node]:\n                return dist\n            neighbors = list(edge_dict[node].keys())\n            for neighbor in neighbors:\n                if neighbor not in seen:\n                    seen[neighbor] = dist+1\n                    frontier.put((neighbor, dist+1))\n                    \n        return -1\n        \n        #if bfs fails return -1\n    \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        stop = {}\n        for i in range(len(routes)):\n            for s in routes[i]:\n                stop[s] = stop.get(s,[]) + [i]\n        for k in stop:\n            stop[k] = set(stop[k])\n        stack = [(S, 0)]\n        visited = set([S])\n        while stack:\n            node, level = stack.pop(0)\n            for bus in stop[node]:\n                for s in set(routes[bus]) - visited:\n                    if s == T:\n                        return level + 1\n                    stack.append((s, level + 1))\n                    visited.add(s)\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        def bfs():\n            Q = []\n            seen = set()\n            for b in busAtStops[S]:\n                Q.append((b, 1))\n            \n            while Q:\n                bus, depth = Q.pop(0)\n                if T in routes[bus]:\n                    return depth\n\n                for stop in routes[bus]:\n                    for bus in busAtStops[stop]:\n                        if bus not in seen:\n                            seen.add(bus)\n                            Q.append((bus, depth+1))\n            return -1            \n        \n        busAtStops = defaultdict(list)\n        for i, r in enumerate(routes):\n            for stop in r:\n                busAtStops[stop].append(i)\n            routes[i] = set(routes[i])\n        \n        return bfs()\n                \n        \n", "from collections import defaultdict, deque\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T or not routes:\n            return 0\n\n        # O(BR)\n        mapping = defaultdict(list)\n        for i, route in enumerate(routes):\n            for start in route:  # , end in zip(route, route[1:]):\n                mapping[start].append(i)\n\n        q = deque([[S, 0]])\n\n        # O(BR)\n        while q:\n            prev_stop, dist = q.popleft()\n\n            if prev_stop not in mapping:\n                continue\n\n            bus_num_li = mapping[prev_stop]\n            # mapping.pop(prev_stop)\n            mapping[prev_stop] = []\n\n            for cur_bus_num in bus_num_li:\n                new_dist = dist + 1\n\n                for cur_stop in routes[cur_bus_num]:\n                    if cur_stop == T:\n                        return new_dist\n\n                    q.append([cur_stop, new_dist])\n\n                routes[cur_bus_num] = []\n\n            # for cur_stop, cur_bus_num in cur_stops.items():\n            #     if cur_stop == T:\n            #         return dist\n            #     q.append([cur_stop, dist + (prev_bus_num or prev_bus_num != cur_bus_num), cur_bus_num])\n\n        return -1\n\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n\n        stop_to_route = defaultdict(list)\n\n        for i in range(len(routes)):\n            for stop in routes[i]:\n                stop_to_route[stop].append(i)\n\n        graph = {}\n\n        for u in range(len(routes)):\n            graph[u] = set()\n\n        for i in range(len(routes)):\n            for stop in routes[i]:\n                for r2 in stop_to_route[stop]:\n                    if r2 != i:\n                        graph[i].add(r2)\n\n        end = set(stop_to_route[T])\n        visited = [False] * len(routes)\n\n        initial = []\n\n        for r in stop_to_route[S]:\n            initial.append((r,1))\n\n        q = deque(initial)\n\n        while q:\n            u,cost = q.popleft()\n\n            if u in end:\n                return cost\n\n            for v in graph[u]:\n                if not visited[v]:\n                    visited[v] = True\n                    q.append((v,cost+1))\n\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: \n            return 0\n        routes = list(map(set, routes))\n        graph = collections.defaultdict(set)\n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n\n        seen, targets = set(), set()\n        for node, route in enumerate(routes):\n            if S in route: \n                seen.add(node)\n            if T in route: \n                targets.add(node)\n\n        queue = [(node, 1) for node in seen]\n        for node, depth in queue:\n            if node in targets: return depth\n            for nei in graph[node]:\n                if nei not in seen:\n                    seen.add(nei)\n                    queue.append((nei, depth+1))\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        def bfs():\n            Q = []\n            seen = set()\n            for b in busAtStops[S]:\n                Q.append((b, 1))\n            \n            while Q:\n                bus, depth = Q.pop(0)\n                if bus not in seen:\n                    seen.add(bus)\n                    if T in routes[bus]:\n                        return depth\n\n                    for stop in routes[bus]:\n                        for bus in busAtStops[stop]:\n                            if bus not in seen:\n                                Q.append((bus, depth+1))\n            return -1            \n        \n        busAtStops = defaultdict(list)\n        for i, r in enumerate(routes):\n            for stop in r:\n                busAtStops[stop].append(i)\n            # routes[i] = set(routes[i])\n        \n        return bfs()\n                \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        '''\n        # BFS\n        # Treat each bus stop as node => TLE\n        # A node is connected with all nodes in the same route(s)\n        # Time: O(V + E)\n        # Space: O(V + E)\n        \n        # Build up adjacency list\n        adj = collections.defaultdict(set)\n        for route in routes:\n            for stop in route:\n                adj[stop].update(route)\n            \n        q = collections.deque()\n        q.append(S)\n        visited = set()\n        visited.add(S)\n        buses = 0\n        while q:\n            for _ in range(len(q)):\n                u = q.popleft()\n                if u == T:\n                    return buses\n                for v in adj[u]:\n                    if v not in visited:\n                        q.append(v)\n                        visited.add(v)\n            buses += 1\n        return -1\n        '''\n        \n        # BFS\n        # Treat each bus route as node\n        # A node is connected with all routes that share a common bus stop\n        \n        # Build up adjacency list\n        adj = collections.defaultdict(set)\n        n = len(routes)\n        for i in range(n):\n            u = routes[i]\n            for j in range(i+1, n):\n                v = routes[j]\n                if set(u).intersection(set(v)):\n                    adj[i].add(j)\n                    adj[j].add(i)\n                    \n        # Build up bus stop -> bus route mapping\n        stop2routes = collections.defaultdict(set)\n        for route, stops in enumerate(routes):\n            for stop in stops:\n                stop2routes[stop].add(route)\n\n        if S == T:\n            return 0\n        \n        adj[-1] = stop2routes[S] # route -1 is connected to all routes that contains S\n        q = collections.deque()\n        q.append(-1)\n        visited = set()\n        visited.add(-1)\n        buses = 0\n        while q:\n            for _ in range(len(q)):\n                u = q.popleft()\n                if u in stop2routes[T]:\n                    return buses\n                for v in adj[u]:\n                    if v not in visited:\n                        visited.add(v)\n                        q.append(v)\n            buses += 1\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        stop_to_bus = collections.defaultdict(set)\n        bus_to_bus = {i: [] for i in range(len(routes))}\n        \n        # end_bus_q = collections.deque([])\n        for bus, route in enumerate(routes):\n            for stop in route:\n                stop_to_bus[stop].add(bus)\n        # print(stop_to_bus, init_bus_q)\n        q = collections.deque(stop_to_bus[S])\n        \n        for i in range(len(routes)):\n            for j in range(i+1, len(routes)):\n                if len(set(routes[i]) & set(routes[j])) > 0:\n                    bus_to_bus[i].append(j)\n                    bus_to_bus[j].append(i)\n        steps = 1\n        visited = [False] * len(routes)\n        # print(visited)\n        while q:\n            size = len(q)\n            for _ in range(size):\n                bus = q.popleft()\n                # print(bus)\n                visited[bus] = True\n                if bus in stop_to_bus[T]:\n                    return steps\n                for nb in bus_to_bus[bus]:\n                    if visited[nb]:\n                        continue\n                    q.append(nb)\n            steps += 1\n        return -1\n            \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        graph = collections.defaultdict(set)\n        num_buses = len(routes)\n        routes = list(map(set, routes))\n        for i, route1 in enumerate(routes):\n            for j in range(i+1, num_buses):\n                route2 = routes[j]\n                \n                if any(r in route2 for r in route1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n        \n        seen, targets = set(), set()\n        for node, route in enumerate(routes):\n            if S in route: seen.add(node)\n            if T in route: targets.add(node)\n        \n        queue = [(node, 1) for node in seen]\n        for node, depth in queue:\n            if node in targets: return depth\n            for neighbour in graph[node]:\n                if neighbour not in seen:\n                    seen.add(neighbour)\n                    queue.append((neighbour, depth+1))\n        \n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        routes = list(map(set, routes))\n        graph = collections.defaultdict(set)\n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n\n        seen, targets = set(), set()\n        for node, route in enumerate(routes):\n            if S in route: seen.add(node)\n            if T in route: targets.add(node)\n\n        queue = [(node, 1) for node in seen]\n        for node, depth in queue:\n            if node in targets: return depth\n            for nei in graph[node]:\n                if nei not in seen:\n                    seen.add(nei)\n                    queue.append((nei, depth+1))\n        return -1\n        \n        \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S==T:\n            return 0\n        maps={}\n        for i in range(len(routes)):\n            r=routes[i]\n            for j in range(len(r)):\n                if r[j] not in maps.keys():\n                    maps[r[j]]=set()\n                maps[r[j]].add(i)\n        res=0\n        lens=len(routes)\n        seenBus=[0]*lens\n        seenStop=set()\n        q=[S]\n        res=0\n        while q:\n            res+=1\n            size=len(q)\n            for i in range(size):\n                stop=q.pop(0)\n                for bus in maps[stop]:\n                    if seenBus[bus]==1:\n                        continue\n                    seenBus[bus]=1\n                    for s in routes[bus]:\n                        if s==T:\n                            return res\n                        if s in seenStop:\n                            continue\n                        seenStop.add(s)\n                        q.append(s)\n                        \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S==T:\n            return 0\n        \n        routes = list(map(set, routes))\n            \n        \n        graph=collections.defaultdict(set)\n        for i,e in enumerate(routes):\n            for j in range(i+1,len(routes)):\n                for node in e:\n                    if node in routes[j]:\n                        graph[i].add(j)\n                        graph[j].add(i)\n        \n        target,start=set(),set()\n        visited=set()\n        \n        for i in range(len(routes)):\n            if S in routes[i]:\n                start.add(i)\n                visited.add(i)\n            if T in routes[i]:\n                target.add(i)\n    \n        step=1\n        while start:\n            nextlevel=set()\n            for node in start:\n                if node in target:\n                    return step\n                for neighbornode in graph[node]:\n                    if neighbornode not in visited:\n                        visited.add(neighbornode)\n                        nextlevel.add(neighbornode)\n            \n            step+=1\n            start=nextlevel\n        \n        return -1", "from collections import defaultdict,deque\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if(S==T):\n            return 0\n        circuits=defaultdict(list)\n        rel={}\n        for i in range(len(routes)):\n            for stand in routes[i]:\n                circuits[stand].append(i)\n                rel[(i,stand)]=1\n        vis={i:1 for i in circuits[S]}\n        vis_bus={S:1}\n        q=deque([i for i in circuits[S]])\n        level=1\n        while q:\n            l=len(q)\n            for i in range(l):\n                curr_cir=q.popleft()\n                if((curr_cir,T) in rel):\n                    return level\n                for bus in routes[curr_cir]:\n                    if bus not in vis_bus:\n                        vis_bus[bus]=1\n                        for cir in circuits[bus]:\n                            if cir not in vis:\n                                q.append(cir)\n                                vis[cir]=1\n            level+=1\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if T == S:\n            return 0\n        possibleStarts = []\n        possibleEnd = []\n        stopGraph = {}\n        for i, route in enumerate(routes):\n            for stop in route:\n                if stop == S:\n                    possibleStarts.append(i)\n                elif stop == T:\n                    possibleEnd.append(i)\n                \n                if stop in stopGraph:\n                    stopGraph[stop].append(i)\n                else:\n                    stopGraph[stop] = [i]\n        \n#         {7: [1, 0, 2],\n#         8: [2, 0, 4]}\n        \n#         { 1:[0, 2],0:[1, 2], 2:[0, 1, 3, 4], 3:[2, 4], 4:[2, 3]}\n        \n        graph = {}\n        for stop in list(stopGraph.keys()):\n            validRoutes = stopGraph[stop]\n            if len(stopGraph[stop]) <= 1:\n                continue\n            for route in validRoutes:\n                if route not in graph:\n                    graph[route] = set()\n                for x in validRoutes:\n                    if x != route:\n                        graph[route].add(x)                  \n        # print(graph)\n        # print(stopGraph)\n        # print(possibleStarts)\n        # print(possibleEnd)\n        queue = [(x, 1) for x in possibleStarts]\n        seen = set()\n        while queue:\n            node = queue.pop(0)\n            seen.add(node[0])\n            if node[0] in possibleEnd:\n                return node[1]\n            if node[0] in graph:\n                children = graph[node[0]]\n            \n                for child in children:\n                    if child not in seen:\n                        queue.append((child, node[1] + 1))\n                        seen.add(child)\n\n            \n                \n        return -1\n        \n                    \n        \n", "        \nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T :\n           return 0 \n        stopToBusDict = defaultdict()\n        \n        for bus in range(len(routes)):\n            for stop in routes[bus]:\n                if stop not in stopToBusDict:\n                   stopToBusDict[stop] = [] \n                stopToBusDict[stop].append(bus)\n    \n        routes = [set(r) for r in routes]\n        \n        adjList = collections.defaultdict(set)\n    \n        \n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    adjList[i].add(j)\n                    adjList[j].add(i)    \n              \n        targets = set()\n        visited = set()\n        for node, route in enumerate(routes):\n            #print(\\\"T: %s node: %s route: %s\\\" %(T,node,route))\n            if T in route: targets.add(node)\n            if S in route: visited.add(node)    \n       \n            \n            \n        def bfs(S,T) :\n            queue = collections.deque()\n            #print(\\\"target: %s\\\" %(targets))\n            for bus in stopToBusDict[S]:\n                queue.append([bus,1])\n            while len(queue) != 0 :\n                \n                currentBus = queue.popleft()\n                visited.add(currentBus[0]) \n                \n                if currentBus[0] in targets:\n                   return currentBus[1]\n                \n                for neighbour in adjList[currentBus[0]] :\n                    if neighbour not in visited :\n                       queue.append([neighbour,currentBus[1]+1])\n            print(-1)        \n            return -1        \n                    \n                \n            \n                \n                \n            \n             \n            \n            \n            \n            \n        return bfs(S,T)      ", "from collections import defaultdict\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T:\n            return 0\n        \n        stop_to_bus_map = defaultdict(list)\n        L = len(routes)\n        for i in range(L):\n            for stop in routes[i]:\n                stop_to_bus_map[stop].append(i)\n                \n        \n        route_graph = defaultdict(set)\n        \n        for stop in stop_to_bus_map:\n            \n            for r1 in stop_to_bus_map[stop]:\n                for r2 in stop_to_bus_map[stop]:\n                    if r1 != r2:\n                        route_graph[r1].add(r2)\n                        \n        \n        start = set(stop_to_bus_map[S])\n        end = set(stop_to_bus_map[T])\n\n        \n        count = 1\n        visited= set()\n        \n        while( len(start) != 0):\n            new_start = set()\n            \n            for route in start:\n                if route in end:\n                    return count\n                if route in visited:\n                    continue\n                \n                new_start |= route_graph[route]\n                \n            \n            visited |= start\n            start = new_start\n            count +=1\n        \n        \n        return -1", "from collections import defaultdict, deque\n\nclass Solution:\n    def bfs(self, start_bus):\n        distance = [None] * self.num_buses\n        distance[start_bus] = 1\n        q = deque([start_bus])\n        while q:\n            bus = q.popleft()\n            if self.target in self.buses_to_stations[bus]:\n                return distance[bus]\n            \n            for station in self.buses_to_stations[bus]:\n                for neighbour_bus in self.stations_to_busses[station]:\n                    if distance[neighbour_bus] is None:\n                        distance[neighbour_bus] = distance[bus] + 1\n                        q.append(neighbour_bus)\n        return 2**32\n        \n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        self.num_buses = len(routes)\n        self.buses_to_stations = [set(route) for route in routes]\n        \n        self.stations_to_busses = defaultdict(list)\n        self.target = T\n        \n        for bus in range(len(routes)):\n            for station in routes[bus]:\n                self.stations_to_busses[station].append(bus)\n        \n        m = 2**32\n        \n        for bus in self.stations_to_busses[S]:\n            dist_by_bus = self.bfs(bus)\n            m = min(m, dist_by_bus)\n        \n        if m == 2**32:\n            return -1\n        else:\n            return m", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        stk = [(S, 0)]\n        stop_dic = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for stop in route:\n                stop_dic[stop].add(i)\n                \n        visited = set()\n        while stk:\n            stop, num_bus = stk.pop(0)\n            if stop == T:\n                return num_bus\n            elif stop not in visited:\n                visited.add(stop)\n                buses = stop_dic[stop]\n                for bus in buses:\n                    for new_stop in routes[bus]:\n                        if new_stop not in visited:\n                            stk.append((new_stop, num_bus + 1))\n                    routes[bus] = []\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S==T:\n            return 0\n        \n        graph = collections.defaultdict(list)\n        bfs = []\n        end = []\n        \n        for i in range(len(routes)):\n            \n            if S in routes[i]:\n                bfs.append((i,1))\n            if T in routes[i]:\n                end.append(i)\n                \n            for j in range(i+1,len(routes)):\n                \n                if set(routes[i]) & set(routes[j]):\n                    \n                    graph[i].append(j)\n                    graph[j].append(i)\n                    \n        \n        bfs = deque(bfs)\n        visited = set(bfs)\n        \n        while bfs:\n            \n            ele = bfs.popleft()\n            \n            bus, nbus = ele\n            \n            if bus in end:\n                return nbus\n            \n            for edge in graph[bus]:\n                if edge not in visited:\n                    visited.add(edge)\n                    bfs.append((edge,nbus+1))\n                    \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        '''\n        # BFS\n        # Treat each bus stop as node => TLE\n        # A node is connected with all nodes in the same route(s)\n        # Time: O(V + E)\n        # Space: O(V + E)\n        \n        # Build up adjacency list\n        adj = collections.defaultdict(set)\n        for route in routes:\n            for stop in route:\n                adj[stop].update(route)\n            \n        q = collections.deque()\n        q.append(S)\n        visited = set()\n        visited.add(S)\n        buses = 0\n        while q:\n            for _ in range(len(q)):\n                u = q.popleft()\n                if u == T:\n                    return buses\n                for v in adj[u]:\n                    if v not in visited:\n                        q.append(v)\n                        visited.add(v)\n            buses += 1\n        return -1\n        '''\n        \n        # BFS\n        # Treat each bus route as node\n        # A node is connected with all routes that share a common bus stop\n        \n        # Build up adjacency list\n        adj = collections.defaultdict(set)\n        n = len(routes)\n        for i in range(n):\n            u = routes[i]\n            for j in range(i+1, n):\n                v = routes[j]\n                if set(u).intersection(set(v)):\n                    adj[i].add(j)\n                    adj[j].add(i)\n                    \n        # Build up bus stop -> bus route mapping\n        stop2route = collections.defaultdict(set)\n        for route, stops in enumerate(routes):\n            for stop in stops:\n                stop2route[stop].add(route)\n\n        if S == T:\n            return 0\n        \n        adj[-1] = set([r for r in range(n) if r in stop2route[S]]) # route -1 is connected to all routes that contains S\n        q = collections.deque()\n        q.append(-1)\n        visited = set()\n        visited.add(-1)\n        buses = 0\n        while q:\n            for _ in range(len(q)):\n                u = q.popleft()\n                if u in stop2route[T]:\n                    return buses\n                for v in adj[u]:\n                    if v not in visited:\n                        visited.add(v)\n                        q.append(v)\n            buses += 1\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        buses = collections.defaultdict(set)\n        count = 0\n        visited = set()\n        \n        for i, route in enumerate(routes):\n            for stop in route:\n                buses[stop].add(i)\n                \n        q = [(S,0)]\n        for stop, count in q:\n            if stop == T:\n                return count\n            for bus in buses[stop]:\n                if bus not in visited:\n                    visited.add(bus)\n                    for next_stop in routes[bus]:\n                        if next_stop != stop:\n                            q.append((next_stop, count+1))\n\n        return -1\n        \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T:\n            return 0\n        \n        routes = [set(route) for route in routes]\n        graph = defaultdict(set)\n        \n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n        \n        visited = set()\n        target = set()\n        for node, route in enumerate(routes):\n            if S in route:\n                visited.add(node)\n            \n            if T in route:\n                target.add(node)\n        \n        q = deque([(node, 1) for node in visited])\n        while q:\n            node, transfer = q.popleft()\n            if node in target:\n                return transfer\n            \n            for neighbor in graph[node]:\n                if neighbor not in visited:\n                    visited.add(neighbor)\n                    q.append((neighbor, transfer + 1))\n        \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S==T:\n            return 0\n        n=len(routes)\n        stop_bus=defaultdict(list)\n        for bus,route in enumerate(routes):\n            for stop in route:\n                stop_bus[stop].append(bus)\n        graph=[[] for _ in range(n)]\n        for bus,route in enumerate(routes):\n            for stop in route:\n                buses=stop_bus[stop]\n                for nei in buses:\n                    if nei!=bus:\n                        graph[bus].append(nei)\n                        graph[nei].append(bus)\n        start=set(stop_bus[S])\n        end=set(stop_bus[T])\n        if start.intersection(end):\n            return 1\n        for s in start:\n            visited=start.copy()\n            q=deque([(s, 1)])\n            while q:\n                cur, l = q.popleft()\n                for nei in graph[cur]:\n                    if nei not in visited:\n                        if nei in end:\n                            return l+1\n                        visited.add(nei)\n                        q.append((nei, l+1))\n        return -1\n                        \n", "from collections import defaultdict\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        adj_list = defaultdict(set)\n        for i,a in enumerate(routes):\n            for k in a:\n                adj_list[k].add(i)\n        q = [[S,0]]\n        visited = {}\n        for stop,path_len in q:\n            if stop==T: return path_len\n            if visited.get(stop)==None:\n                for route in adj_list[stop]:\n                    for k in routes[route]:\n                        q.append([k,path_len+1])\n                visited[stop] = True\n                routes[route] = []\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        n = len(routes)\n        graph = collections.defaultdict(list)\n        sources = set()\n        targets = set()\n        for i in range(n):\n            if S in routes[i]:\n                sources.add(i)\n            if T in routes[i]:\n                targets.add(i)\n            for j in range(i+1, n):\n                if set(routes[i]) & set(routes[j]):\n                    graph[i].append(j)\n                    graph[j].append(i)\n        \n        dist = 1\n        seen = set()\n        while sources:\n            temp = set()\n            for curr in sources:\n                if curr in targets:\n                    return dist\n                for neighbor in graph[curr]:\n                    if neighbor not in seen:\n                        seen.add(neighbor)\n                        temp.add(neighbor)\n            sources = temp\n            dist += 1\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if not routes:\n            return -1\n        bus2stop = collections.defaultdict(set)\n        stop2bus = collections.defaultdict(set)\n        for bus, route in enumerate(routes):\n            for stop in route:\n                bus2stop[bus].add(stop)\n                stop2bus[stop].add(bus)\n                \n                \n        q = collections.deque()\n        q.append((0, S))\n        seen = set()\n        seen.add(S)\n        while q:\n            hop, curStop = q.popleft()\n            if curStop==T:\n                return hop\n            for bus in stop2bus[curStop]:\n                for nxtStop in bus2stop[bus]:\n                    if nxtStop not in seen:\n                        seen.add(nxtStop)\n                        q.append((hop+1, nxtStop))\n                        \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        \n        b2b = collections.defaultdict(list)\n        s2b = collections.defaultdict(list)\n        for i in range(len(routes)):\n            for s in routes[i]: s2b[s].append(i)\n            for j in range(i+1, len(routes)):\n                if set(routes[i]) & set(routes[j]):\n                    b2b[i].append(j)\n                    b2b[j].append(i)\n                    \n        q = collections.deque([[b, 1] for b in s2b[S]])\n        seen = set()\n        while q:\n            b, lvl = q.popleft()\n            if b in seen: continue\n            seen.add(b)\n            if T in routes[b]: return lvl\n            for b2 in b2b[b]: \n                if b2 not in seen: q.append([b2, lvl+1])\n        return -1", "import heapq\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T:\n            return 0\n        \n        graph = defaultdict(list)\n        \n        routes_set = []\n        for route in routes:\n            routes_set.append(set(route))\n            \n        for i, r1 in enumerate(routes_set):\n            for j in range(i+1, len(routes_set)):\n                r2 = routes_set[j]\n                \n                if any([r in r2 for r in r1]):\n                    graph[i].append(j)\n                    graph[j].append(i)\n                    \n                    \n        \n        target = set()\n        visited = set()\n        for i, r in enumerate(routes_set):\n            if S in r:\n                visited.add(i)\n            if T in r:\n                target.add(i)\n                \n        queue = [(bus, 1) for bus in visited]\n        while queue:\n            bus, moves = queue.pop(0)\n            if bus in target:\n                return moves\n            \n            for nei in graph[bus]:\n                if nei not in visited:\n                    visited.add(nei)\n                    queue.append((nei, moves+1))\n                    \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T: return 0\n        routes = list(map(set, routes))\n        graph = defaultdict(set)\n        for i in range(0, len(routes)):\n            for j in range(i+1, len(routes)):\n                if any(r in routes[j] for r in routes[i]):\n                    graph[i].add(j)\n                    graph[j].add(i)\n                \n        src = set()\n        dest = set()\n        for index, route in enumerate(routes):\n            if S in route: src.add(index)\n            if T in route: dest.add(index)\n                \n        queue = deque()\n        for node in src:\n            queue.append((node, 1))\n        \n        while queue:\n            node,step = queue.popleft()\n            if node in dest: return step\n            for nei in graph[node]:\n                if nei not in src:\n                    src.add(nei)\n                    queue.append((nei,step+1))\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T: return 0\n        routes = list(map(set, routes))\n        graph = defaultdict(set)\n        for i in range(0, len(routes)):\n            for j in range(i+1, len(routes)):\n                if any(r in routes[j] for r in routes[i]):\n                    graph[i].add(j)\n                    graph[j].add(i)\n                \n        src = set()\n        dest = set()\n        for index, route in enumerate(routes):\n            if S in route: src.add(index)\n            if T in route: dest.add(index)\n                \n        queue = deque()\n        for node in src:\n            queue.append((node, 1))\n        \n        seen = set()\n        while queue:\n            node,step = queue.popleft()\n            if node in dest: return step\n            for nei in graph[node]:\n                if nei not in src:\n                    src.add(nei)\n                    queue.append((nei,step+1))\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        #can it go back to prev node??\n        if S==T:\n            return 0\n        \n        \n        routes_map = {}\n        graph = {} #bus stop -> route no.\n        for i in range(len(routes)):\n            routes_map[i] = set()\n            for j in range(len(routes[i])):\n                routes_map[i].add(routes[i][j])\n                if routes[i][j] not in graph:\n                    graph[routes[i][j]] = set()\n                graph[routes[i][j]].add(i)\n                \n                \n        #find the route which contains Start point, and add all the busstops in that route\n        queue = []\n        visited = set()\n        bus_stop_visited = set()\n\n        for route in routes_map:\n            if S in routes_map[route]: #the start point can have multiple bus routes\n                for bus_stop in routes_map[route]:\n                    queue.append((bus_stop, route))\n                    bus_stop_visited.add(bus_stop)\n                visited.add(route)\n                \n        path = 1\n        while queue:\n            length = len(queue)\n            for i in range(len(queue)):\n                bus_stop, route = queue.pop(0)\n                #Goal check\n                if T in routes_map[route]:\n                    return path\n                for neighbor_route in graph[bus_stop]:\n                    if neighbor_route not in visited:\n                        for neighbor_bus_stop in routes_map[neighbor_route]:\n                            if neighbor_bus_stop not in bus_stop_visited:\n                                bus_stop_visited.add(neighbor_bus_stop)\n                                queue.append((neighbor_bus_stop, neighbor_route))\n                                \n                        visited.add(neighbor_route)\n                \n            path += 1\n        \n        return -1\n            \n        \n                \n        \n        \n        \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        for i in range(len(routes)):\n            routes[i] = set(routes[i])\n        \n        start_bus = set()\n        end_bus = set()\n        connections = collections.defaultdict(set)\n        for i in range(len(routes)):\n            busA = routes[i]\n            \n            if S in busA:\n                start_bus.add(i)\n                \n            if T in busA:\n                end_bus.add(i)\n            \n            for j in range(len(routes)):\n                if i == j:\n                    continue\n                    \n                busB = routes[j]\n                if len(busA & busB):\n                    connections[i].add(j)\n                   \n        if start_bus == end_bus:\n            return 1 if S != T else 0\n\n        S = list(start_bus)[0]\n        T = list(end_bus)[0]\n                    \n        # print(start_bus, end_bus, connections)\n        \n        # connections = collections.defaultdict(set)\n        # for r in routes:\n        #     for i in range(len(r)):\n        #         for j in range(len(r)):\n        #             if i != j:\n        #                 connections[r[i]].add(r[j])\n\n        first_hop = 1\n        # q = [(first_hop, S)]\n        \n        q = [(1, s) for s in start_bus]\n        \n        seen = set()\n\n        ans = float('inf')\n        while q:\n            # print(q)\n            W, C = heapq.heappop(q)\n            \n            if C in end_bus:\n                end_bus.remove(C)\n                \n                ans = min(ans, W)\n                \n                if not end_bus:\n                    break\n            \n            if C in seen:\n                continue\n\n            seen.add(C)\n\n            W += 1\n            for i in connections[C]:\n                if i not in seen:\n                    heapq.heappush(q, (W, i))\n        \n        return -1 if ans == float('inf') else ans\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        graph = collections.defaultdict(list)\n        \n        for i,stops in enumerate(routes):\n            for stop in stops:\n                graph[stop].append(i)\n                \n        que = graph[S]\n        visited = set()\n        steps = 0\n        while que:\n            tmp = []\n            for bus in que:\n                if bus in visited:\n                    continue\n                visited.add(bus)\n                for stop in routes[bus]:\n                    if stop == T:\n                        return steps + 1\n                    for bus2 in graph[stop]:\n                        if bus2 not in visited:\n                            tmp.append(bus2)\n                            \n            que = tmp\n            steps += 1\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        # BFS\n        if S == T:\n            return 0\n\n        N = len(routes)\n        graph = dict()\n        \n        for i in range(N):\n            routes[i] = set(routes[i])\n        \n        for i in range(N):\n            if i not in graph:\n                graph[i] = set()\n                \n            for j in range(i+1, N):\n                if j not in graph:\n                    graph[j] = set()\n                    \n                if i != j:\n                    if any(node in routes[i] for node in routes[j]):\n                        graph[i].add(j)\n                        graph[j].add(i)\n        s = set()\n        t = set()\n        \n        for i, route in enumerate(routes):\n            if S in route:\n                s.add(i)\n            if T in route:\n                t.add(i)\n                \n        if any(node in s for node in t):\n            return 1\n        \n        queue = [[i, 1] for i in s]\n        visited = s\n        \n        for node, d in queue:\n            for nxt in graph[node]:\n                if nxt not in visited:\n                    if nxt in t:\n                        return d + 1\n                    visited.add(nxt)\n                    queue.append([nxt, d+1])\n                    \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        # want a graph such that buses with something in common are neighbors \n        # then can just check if desired stop in the stop set, then return the level of a bfs traversal\n        # queue would just be then initally all bus with S in them, can trivally return 1 I believe\n        \n        # O(n**2)\n        # the question is how to construct a graph quickly, what is the point if the graph construction takes O(n**3) or worse?\n        # especially with the shit with routes[i].length being ridiculous\n        # iterate through i\n        # iterate through routes[i]\n        # add all buses as neighbors? That's pretty awful construction\n        \n        if  S == T:\n            return 0\n        routes = [set(j) for j in routes]\n        # looks like triple iteration will work jesus \n        graph = {}\n        \n        for bus, route in enumerate(routes):\n            graph.setdefault(bus,[])\n\n            for other_bus in range(bus+1, len(routes)):\n\n                if any(r in routes[other_bus] for r in route):\n                    graph[bus].append(other_bus)\n                    graph.setdefault(other_bus, [])\n                    graph[other_bus].append(bus)\n        level = 1\n        queue = [i for i in range(len(routes)) if S in routes[i]]\n        seen = set()\n        for bus in queue:\n            seen.add(bus)\n        while queue:\n            new_queue = []\n            for bus in queue:\n                if T in routes[bus]:\n                    return level\n                for neighbor_bus in graph[bus]:\n                    if neighbor_bus not in seen:\n                        seen.add(neighbor_bus)\n                        new_queue.append(neighbor_bus)\n            queue = new_queue\n            level += 1\n\n        return -1\n                \n", "from queue import Queue\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n\n        stopToBus = {}\n        for bus in range(len(routes)):\n            for stop in routes[bus]:\n                stopToBus.setdefault(stop, set())\n                stopToBus[stop].add(bus)\n        \n        q = Queue(maxsize=1000000)\n        busVis = [False] * len(routes)\n        stopVis = [False] * 1000000\n        q.put((S, 0))\n        while q.qsize() > 0:\n            stop, dist = q.get()\n            stopVis[stop] = True\n            for bus in stopToBus[stop]:\n                if busVis[bus] == False:\n                    busVis[bus] = True\n                    for ds in routes[bus]:\n                        if stopVis[ds] == False:\n                            if ds == T:\n                                return dist + 1\n\n                            q.put((ds, dist + 1))\n        \n        return -1", "class Solution:\n    # bfs\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n\n        md, que, visited, changes = collections.defaultdict(set), collections.deque(), set(), {}\n\n        # prre-processing, we can get dict m[1] = (0), m[2] = (0), m[7] = (0,1) ,etc\n        # means for stop 7 , bus 0, and 1 can reach\n        for b, r in enumerate(routes):\n            for s in r:\n                md[s].add(b)\n\n        # S or T not reachable\n        if S not in md or T not in md:\n            return -1\n\n        # if S and T are same, we don't even need to take bus\n        if S == T:\n            return 0\n\n        for b in md[S]:\n            for stop in routes[b]:\n                # (2,0,0), (7,0,0)\n                # (1,0,0) - means stop 1, bus 0, bus changes 0\n                que.append((stop, b, 1))\n                # changes[1,0] = 0, changes[2,0] = 0, changes[7,0] = 0\n                # means for reach 1,2,7 we just 1 times of bus change\n                # (take the first bus also count as 1 change)\n                changes[stop, b] = 1\n\n        while que:\n            stop, bus, times = que.popleft()\n            # already reach the Target\n            if stop == T:\n                return times\n            for b in md[stop]:\n                if bus != b:\n                    for stop in routes[b]:\n                        # if I already reached this stop by bus, but I used few times for change\n                        if (stop, bus) in changes and changes[stop, bus] > 1 + times:\n                            que.append((stop, bus, 1 + times))\n                            # remember update the new times in cache\n                            changes[stop, bus] = 1 + times\n                        elif (stop, bus) not in changes:  # I never reached stop by this bus yet\n                            changes[stop, bus] = 1 + times\n                            que.append((stop, bus, 1 + times))\n                        # else: if I reached stop by bus, but I changed more times than the record in cache,\n                        # just prunning it\n                    # this sentences improve the performance greatly\n                    # the time is from 5000ms decrease to 260 ms\n                    routes[b] = []\n\n        return -1\n\n    # dijkstra\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n\n        md, heap, visited, changes = collections.defaultdict(set), [], set(), set()\n\n        # prre-processing, we can get dict m[1] = (0), m[2] = (0), m[7] = (0,1) ,etc\n        # means for stop 7 , bus 0, and 1 can reach\n        for b, r in enumerate(routes):\n            for s in r:\n                md[s].add(b)\n\n        # S or T not reachable\n        if S not in md or T not in md:\n            return -1\n\n        # if S and T are same, we don't even need to take bus\n        if S == T:\n            return 0\n\n        for b in md[S]:\n            for stop in routes[b]:\n                # for test case: [[1,2,7],[3,6,7]], 1, 6\n                # we got (1,0,2), (1,0,7)\n                # means from stop 1 to go to stop 2 and 7, we just need to take one bus (1 changes )\n                heapq.heappush(heap, (1, b, stop))\n                # changes[1,0] = 0, changes[2,0] = 0, changes[7,0] = 0\n                # means for reach 1,2,7 we just 1 times of bus change\n                # (take the first bus also count as 1 change)\n                changes.add((stop, b))\n\n        while heap:\n            times, bus, stop = heapq.heappop(heap)\n            # already reach the Target\n            if stop == T:\n                return times\n            for b in md[stop]:\n                if bus != b:\n                    for stop in routes[b]:\n                        if (stop, bus) not in changes:  # I never reached stop by this bus yet\n                            changes.add((stop, bus))\n                            heapq.heappush(heap, (1 + times, bus, stop))\n        return -1\n\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n\n        if S == T:\n            return 0\n        graph = collections.defaultdict(set)\n\n        routes = list(map(set, routes))\n\n        for k1, r1 in enumerate(routes):\n            for k2 in range(k1 + 1, len(routes)):\n                if any(stop in routes[k2] for stop in r1):\n                    graph[k1].add(k2)\n                    graph[k2].add(k1)\n\n        seen, targets = set(), set()\n        for k, r in enumerate(routes):\n            if S in r:\n                seen.add(k)\n            if T in r:\n                targets.add(k)\n\n        que = [(node, 1) for node in seen]\n\n        while que:\n            node, depth = que.pop(0)\n            if node in targets:\n                return depth\n            for nei in graph[node]:\n                if nei not in seen:\n                    seen.add(nei)\n                    que.append((nei, depth + 1))\n\n        return -1\n\n\n", "from collections import defaultdict\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S==T:\n            return 0\n        \n        routes = [set(x) for x in routes]\n        \n        stops = defaultdict(list)\n        for i in range(len(routes)):\n            for s in routes[i]:\n                stops[s].append(i)\n        \n        #bfs\n        curr_layer = [i for i, x in enumerate(routes) if S in x]\n        next_layer = []\n        num_routes = 1\n        seen = set(curr_layer)\n        \n        while curr_layer:\n            for i in curr_layer:\n                \n                if T in routes[i]:\n                    return num_routes\n                \n                for j in routes[i]:\n                    for k in stops[j]:\n                        if k not in seen:\n                            seen.add(i)\n                            next_layer.append(k)\n                \n            \n            curr_layer = next_layer\n            next_layer = []\n            num_routes += 1\n            \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        queue = collections.deque()\n        dic_buses = collections.defaultdict(set)\n        dic_stops = collections.defaultdict(set)\n        visited_buses = set()\n        for i, stops in enumerate(routes):\n            dic_buses[i] = set(stops)\n            if S in dic_buses[i]:\n                if T in dic_buses[i]: return 1\n                visited_buses.add(i)\n                queue.append(i)\n            for j in dic_buses[i]:\n                dic_stops[j].add(i)\n        bus_need = 2\n        visited_stops = set()\n        while queue:\n            length = len(queue)\n            for _ in range(length):\n                bus = queue.popleft()\n                for stop in dic_buses[bus]:\n                    if stop in visited_stops: continue\n                    visited_stops.add(stop)\n                    for b in dic_stops[stop]:\n                        if b not in visited_buses:\n                            if T in dic_buses[b]:\n                                return bus_need\n                            queue.append(b)\n                            visited_buses.add(b)\n            bus_need += 1\n        return -1\n                            \n                \n                \n", "class Solution: # 368 ms\n    def numBusesToDestination(self, routes, start, target):\n        if start == target: return 0\n\n        stop2Route = defaultdict(set)\n        route2Stop = defaultdict(set)\n        for i, stops in enumerate(routes):\n            for stop in stops:\n                route2Stop[i].add(stop)\n                stop2Route[stop].add(i)\n\n      #  visited = set() \n        visitedStop = set()       \n        \n        curr, other = {start}, {target}\n        step = 0\n        while curr and other:\n            stack = set()\n            step += 1\n            while curr:\n                stop = curr.pop()\n                visitedStop.add(stop)\n                for route in stop2Route[stop]:\n                    if route in route2Stop:\n                        for stop in routes[route]:\n                            if stop not in visitedStop:\n                                stack.add(stop)\n                        del route2Stop[route] \n            if stack & other: return step\n            curr = stack\n            if len(curr) > len(other):    \n                curr, other = other, curr\n\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        # build graph, with each route being a vertex of the graph\n        graph = collections.defaultdict(list)\n        for i in range(len(routes)):\n            for j in range(i+1, len(routes)):\n                # if two routes share any common stops, they are neighbors\n                if set(routes[i]) & set(routes[j]):\n                    graph[tuple(routes[i])].append(tuple(routes[j]))\n                    graph[tuple(routes[j])].append(tuple(routes[i]))\n        \n        # BFS all routes to find shortest path between any two routes containing \n        # S and T respectively\n        min_buses = float('inf')\n        for route in graph:\n            visited = set()\n            if S in route:\n                queue = collections.deque([(route, 1)])\n                visited.add(route)\n                while queue:\n                    route, num_buses = queue.popleft()\n                    if T in route:\n                        min_buses = min(min_buses, num_buses)\n                        break\n                    for nei in graph[route]:\n                        if nei not in visited:\n                            visited.add(nei)\n                            queue.append((nei, num_buses+1))\n        \n        return min_buses if min_buses != float('inf') else -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], source: int, destination: int) -> int:\n        # 1 - 2 - 7\n        #         7 - 3 - 6\n        #             3 - 5\n        #     2 --------- 5 - 8\n        if not routes:\n            return -1\n        \n        if source == destination:\n            return 0\n        \n        graph = collections.defaultdict(list)\n        for i, route in enumerate(routes):\n            for stop in route:\n                graph[stop].append(i)\n        \n        routes = [set(route) for route in routes]\n\n        sources = [[source, route, 1] for route in graph[source]]\n        q, visited = collections.deque(sources), set()\n        while q:\n            stop, route, bus = q.popleft()\n            if stop == destination or destination in routes[route]:\n                return bus\n            visited.add((stop, route))\n            for nxt_stop in routes[route]:\n                if len(graph[nxt_stop]) == 1: continue\n                if (nxt_stop, route) not in visited:\n                    q.append((nxt_stop, route, bus))\n                    for nxt_route in graph[nxt_stop]:\n                        if nxt_route != route:\n                            q.append((nxt_stop, nxt_route, bus + 1))\n        return -1\n                \n", "from collections import defaultdict, deque\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        graph = defaultdict(set)\n        \n        for bus, route in enumerate(routes):\n            for r in route:\n                graph[r].add(bus)\n        \n        # print(graph)\n        \n        queue = deque([(S,0)])\n        seen = set([S])\n        \n        while queue:\n            stop, busCnt = queue.popleft()\n            if stop == T:\n                return busCnt\n            for bus in graph[stop]:\n                for stp in routes[bus]:\n                    if stp not in seen:\n                        queue.append((stp, busCnt+1))\n                        seen.add(stp)\n        return -1", "from collections import defaultdict, deque\n\nclass Solution:\n    \n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T:\n            return 0\n        \n        mapping = defaultdict(list)\n        routes_mapping = defaultdict(set)\n        stations_in_route = {}\n        \n        seen = set()\n        \n        for i, bus in enumerate(routes):\n            \n            stations_in_route[i] = set(bus)\n            \n            for station  in bus:\n                \n                if station in mapping:\n                    new_mapping = set(mapping[station])\n                    routes_mapping[i] = routes_mapping[i] | new_mapping\n                    \n                    for b in mapping[station]:\n                        routes_mapping[b].add(i)\n                \n                mapping[station].append(i)\n        \n        queue = deque(mapping[S])\n        seen = set(mapping[S])\n        \n        buses = 1\n        \n        while queue:\n            \n            for _ in range(len(queue)):\n                \n                bus = queue.popleft()\n                \n                if T in stations_in_route[bus]:\n                    return buses\n            \n                for next_route in routes_mapping[bus]:\n                    if next_route not in seen:\n                        seen.add(next_route)\n                        queue.append(next_route)\n            \n            buses += 1\n        \n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], source: int, destination: int) -> int:\n        # 1 - 2 - 7\n        #         7 - 3 - 6\n        #             3 - 5\n        #     2 --------- 5 - 8\n        if not routes:\n            return -1\n        \n        if source == destination:\n            return 0\n        \n        connections = collections.defaultdict(list)\n        for i, route in enumerate(routes):\n            for stop in route:\n                connections[stop].append(i)\n        \n        routes = [set(route) for route in routes]\n\n        sources = [[source, route, 1] for route in connections[source]]\n        q, visited = collections.deque(sources), set()\n        while q:\n            stop, route, bus = q.popleft()\n            if stop == destination or destination in routes[route]:\n                return bus\n            visited.add((stop, route))\n            for nxt_stop in routes[route]:\n                if len(connections[nxt_stop]) == 1: continue\n                if (nxt_stop, route) not in visited:\n                    q.append((nxt_stop, route, bus))\n                    for nxt_route in connections[nxt_stop]:\n                        if nxt_route != route:\n                            q.append((nxt_stop, nxt_route, bus + 1))\n        return -1\n                \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        stop_to_bus = collections.defaultdict(list)\n        for i in range(len(routes)):\n            for stop in routes[i]:\n                stop_to_bus[stop].append(i)\n        bus_to_stop = routes\n        \n        queue = collections.deque([S])\n        visited_bus = set()\n        level = 0\n        while queue:\n            for _ in range(len(queue)):\n                stop = queue.popleft()\n                if stop == T:\n                    return level\n                for bus in stop_to_bus[stop]:\n                    if bus in visited_bus:\n                        continue\n                    visited_bus.add(bus)\n                    for next_stop in bus_to_stop[bus]:\n                        queue.append(next_stop)\n            level += 1\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        graph = collections.defaultdict(set)\n        for i in range(len(routes)):\n            for j in range(i + 1, len(routes)):\n                if set(routes[i]) & set(routes[j]): \n                    graph[i].add(j)\n                    graph[j].add(i)\n        routeSet = [set(route) for route in routes]\n        startRoutes = [i for i in range(len(routes)) if S in routeSet[i]]\n        q, visited = deque([(i, 1) for i in startRoutes]), set(startRoutes)\n        while q:\n            r, step = q.popleft()\n            if T in routeSet[r]: return step\n            for nr in graph[r]:\n                if nr not in visited:\n                    visited.add(nr)\n                    q += (nr, step + 1),\n        return -1", "from collections import deque\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        def bfs(graph, routes, visited, start_bus, T):\n            \n            queue = deque()\n            queue.append([start_bus, 1])\n            \n            while queue:\n                bus, count = queue.popleft()\n                visited.add(bus)\n                \n                if T in routes[bus]:\n                    return count\n                \n                else:\n                    for neighbor in graph[bus]:\n                        if neighbor not in visited:\n                            queue.append([neighbor, count+1])\n            \n            return float('inf')\n        \n        if S == T:\n            return 0\n        \n        routes = list(map(set, routes))\n        graph = collections.defaultdict(set)\n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n        \n        result = float('inf')\n        for bus in range(len(routes)):\n            if S in routes[bus]:\n                min_path = bfs(graph, routes, set(), bus, T)\n                result = min(result, min_path)\n        \n        if result == float('inf'):\n            return -1\n        \n        return result\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        #build graph of bus_stop: routes\n        \n        graph= {}\n        for i in range(len(routes)):\n            for j in range(len(routes[i])):\n                if routes[i][j] not in graph:\n                    graph[routes[i][j]] = set()\n                graph[routes[i][j]].add(i)\n                \n        visited_bus_stops = set()\n        queue = []\n        #initialize queue with the initial bus stop\n        queue.append(S)\n        visited_bus_stops.add(S)\n\n        distance = 0\n        while queue:\n            length = len(queue)\n            for i in range(length):\n                bus_stop = queue.pop(0)\n                if bus_stop == T:\n                    return distance\n\n                for route in graph[bus_stop]:\n                    for stop in routes[route]:\n                        if stop not in visited_bus_stops:\n                            queue.append(stop)\n                            visited_bus_stops.add(stop)\n                    \n                    routes[route] = []\n            distance += 1\n        \n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T:\n            \n            return 0\n        \n        routes = [set(route) for route in routes]\n        \n        reachable = collections.defaultdict(list)\n        \n        for i in range(len(routes)):\n            \n            for j in range(i + 1, len(routes)):\n                \n                if any([stop in routes[j] for stop in routes[i]]):\n                    \n                    reachable[i].append(j)\n                    \n                    reachable[j].append(i)\n        \n        target_routes = set()\n        \n        q = []\n        \n        visited = set()\n        \n        for i in range(len(routes)):\n            \n            if S in routes[i]:\n                \n                q.append((i, 1))\n                \n                visited.add(i)\n                \n            if T in routes[i]:\n                \n                target_routes.add(i)\n                \n        while q:\n            \n            route, count = q.pop(0)\n            \n            if route in target_routes:\n                \n                return count\n            \n            for next_route in reachable[route]:\n                \n                if next_route not in visited:\n                    \n                    visited.add(next_route)\n                    \n                    q.append((next_route, count + 1))\n                    \n        return -1\n        \n        \n        \n        \n        \n        \n        \n        \n                    \n        \n", "from queue import deque\n\ndef bfs(adjList, s, t):\n    END = '$'\n    queue = deque([s, END])\n    visited = set()\n    step = 0\n    while queue:\n        node = queue.popleft()\n        \n        if node == t:\n            return step\n        \n        if node == END:\n            if not queue:\n                break\n            step += 1\n            queue.append(END)\n            continue\n            \n        visited.add(node)\n        for adjNode in adjList[node]:\n            if adjNode not in visited:\n                queue.append(adjNode)\n    return -1\n\ndef numBusesToDestination_Graph_TLE(routes, S, T):\n    adjList = {}\n    for route in routes:\n        for i in range(len(route)):\n            if route[i] not in adjList:\n                adjList[route[i]] = set()\n            for j in range(i+1, len(route)):\n                if route[j] not in adjList:\n                    adjList[route[j]] = set()\n                adjList[route[i]].add(route[j])\n                adjList[route[j]].add(route[i])\n    if S not in adjList:\n        return -1\n    return bfs(adjList, S, T)\n\ndef numBusesToDestination_GraphTakeRouteAsNod_TLE(routes, S, T):\n    if S == T:\n        return 0\n    adjList = {\n        'S': set(), 'T': set()\n    }\n    \n    for i in range(len(routes)):\n        routes[i] = set(routes[i])\n        adjList[i] = set()\n        if S in routes[i]:\n            adjList['S'].add(i)\n        if T in routes[i]:\n            adjList[i].add('T')\n    \n    for i in range(len(routes)):\n        for j in range(i+1, len(routes)):\n            if any([k in routes[j] for k in routes[i]]):\n                adjList[i].add(j)\n                adjList[j].add(i)\n    return max(bfs(adjList, 'S', 'T') - 1, -1)\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        # return numBusesToDestination_Graph_TLE(routes, S, T)\n        return numBusesToDestination_GraphTakeRouteAsNod_TLE(routes, S, T)", "class Solution:        \n    def numBusesToDestination(self, routes, S, T):\n        if S == T:\n            return 0\n        stop_to_bus = collections.defaultdict(list)\n        for bus,stops in enumerate(routes):\n            for stop in stops:\n                stop_to_bus[stop].append(bus)\n        \n        q = collections.deque([S])\n        seen_bus = set()\n        seen_stop = set()\n        step = -1\n        while q:\n            step += 1\n            for _ in range(len(q)):\n                stop = q.popleft()\n                if stop == T:\n                    return step\n                for bus in stop_to_bus[stop]:\n                    if bus in seen_bus:\n                        continue\n                    seen_bus.add(bus)\n                    for next_stop in routes[bus]:\n                        if next_stop in seen_stop:\n                            continue\n                        q.append(next_stop)\n                        seen_stop.add(stop)\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        mapping = dict() # key is bus stop, val is bus number\n        for bus, stops in enumerate(routes): \n            for stop in stops: \n                if stop not in mapping: \n                    mapping[stop] = []\n                mapping[stop].append(bus)\n        \n        queue = []\n        stop_visited = set()\n        bus_visited = set()\n        queue.append((S, 0))\n        while queue: \n            current, numBuses = queue.pop(0)\n            if current == T: \n                return numBuses\n            stop_visited.add(current)\n            for bus in mapping[current]: \n                if bus not in bus_visited:\n                    bus_visited.add(bus)\n                    for stop in routes[bus]:\n                        if stop not in stop_visited: \n                            queue.append((stop, numBuses+1))\n        return -1", "from collections import defaultdict, deque\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], source_stop: int, target_stop: int) -> int:\n        if source_stop == target_stop: return 0\n        routes = [set(r) for r in routes]\n        stops = defaultdict(set)\n        for i,route in enumerate(routes):\n            for stop in route:\n                stops[stop].add(i)\n        q = deque()\n        visited_stops = set()\n        # visited_buses = set()\n        q.append((source_stop, 0))\n        while q:\n            stop_num, bus_num = q.popleft()\n            visited_stops.add(stop_num)\n            for other_bus in stops[stop_num]:\n                # if other_bus in visited_buses: continue\n                for other_stop in routes[other_bus]:\n                    if other_stop == target_stop:\n                        return bus_num + 1\n                    if other_stop not in visited_stops:\n                        visited_stops.add(other_stop)\n                        q.append((other_stop, bus_num + 1))\n        return -1\n\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        visited = set()\n        stop_bus = collections.defaultdict(list)\n        for i in range(len(routes)):\n            for stop in routes[i]:\n                stop_bus[stop].append(i)\n        # print(stop_bus)\n        stops = collections.deque([(S, 0, 0)])\n        \n        while stops:\n            cur_stop, n, taken = stops.popleft()\n            # print(cur_stop, n, taken)\n            if cur_stop == T:\n                return n\n            \n            if cur_stop not in visited:\n                next_stop = set()\n                visited.add(cur_stop)\n                for bus in stop_bus[cur_stop]:\n                    # print(bus, taken, bus+1&taken)\n                    if pow(2, bus) & taken == 0:  # never take the bus before\n                        for stop in routes[bus]:\n                            if stop in next_stop:\n                                continue\n                            next_stop.add(stop)\n                            stops.append((stop, n+1, taken | pow(2, bus)))\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        n = len(routes)\n        graph = defaultdict(set)\n        \n        for i, r in enumerate(routes):\n            for s in r:\n                graph[s].add(i)\n        \n        q = [(S, 0)]\n        visit = set()\n        visit.add(S)\n\n        while q:\n            cur, dis = q.pop(0)\n            \n            if cur == T:\n                return dis\n            \n            for r in graph[cur]:\n                for j in routes[r]:\n                    if j not in visit:\n                        q.append((j, dis+1))\n                        visit.add(j)\n \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        adj_list = collections.defaultdict(set)\n        for i in range(len(routes)):\n            for j in range(len(routes[i])):\n                adj_list[routes[i][j]].add(i)\n        queue = collections.deque([(S,0)])\n        visited = set()\n        while queue:\n            node,taken = queue.popleft()\n            if node == T:\n                return taken\n            for i in adj_list[node]:\n                for j in routes[i]:\n                    if j not in visited:\n                        visited.add(j)\n                        queue.append((j,taken+1))\n        return -1\n                \n", "class Solution: # 368 ms\n    def numBusesToDestination(self, routes, start, target):\n        if start == target: return 0\n\n        stop2Route = defaultdict(set)\n        route2Stop = defaultdict(set)\n        for i, stops in enumerate(routes):\n            for stop in stops:\n                route2Stop[i].add(stop)\n                stop2Route[stop].add(i)\n\n        visited = set() \n        visitedStop = set()       \n        \n        curr, other = {start}, {target}\n        step = 0\n        while curr and other:\n            stack = set()\n            step += 1\n            while curr:\n                stop = curr.pop()\n                visitedStop.add(stop)\n                for route in stop2Route[stop]:\n                    if route in route2Stop:\n                        for stop in routes[route]:\n                            if stop not in visitedStop:\n                                stack.add(stop)\n                        del route2Stop[route] \n            if stack & other: return step\n            curr = stack\n            if len(curr) > len(other):    \n                curr, other = other, curr\n\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        adj_list = collections.defaultdict(set)\n        for i in range(len(routes)):\n            for j in range(len(routes[i])):\n                adj_list[routes[i][j]].add(i)\n        queue = collections.deque([(S,0)])\n        visited = set()\n        visited.add(S)\n        while queue:\n            node,taken = queue.popleft()\n            if node == T:\n                return taken\n            for i in adj_list[node]:\n                for j in routes[i]:\n                    if j not in visited:\n                        visited.add(j)\n                        queue.append((j,taken+1))\n        return -1\n                \n", "class Solution:\n    def numBusesToDestination(self, routes, originStop, destinationStop):\n        stopToBus = collections.defaultdict(set)\n        for bus, stops in enumerate(routes):\n            for stop in stops:\n                stopToBus[stop].add(bus)\n        from collections import deque \n        dq = deque([[originStop, 0]])\n        visited = set()\n        visited.add(originStop)\n        while dq:\n            stop, numOfBuses = dq.popleft()\n            if stop == destinationStop:\n                return numOfBuses \n            for bus in stopToBus[stop]:\n                for nextStop in routes[bus]:\n                    if nextStop not in visited:\n                        visited.add(nextStop)\n                        dq.append([nextStop, numOfBuses+1])\n        return -1 \n                        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        stop = {}\n        for i in range(len(routes)):\n            for s in routes[i]:\n                stop[s] = stop.get(s,[]) + [i]\n        for k in stop:\n            stop[k] = set(stop[k])\n        stack = [(S, 0)]\n        visited = set([S])\n        while stack:\n            node, level = stack.pop(0)\n            for bus in stop[node]:\n                for s in routes[bus]:\n                    if s in visited:\n                        continue\n                    if s == T:\n                        return level + 1\n                    stack.append((s, level + 1))\n                    visited.add(s)\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        stop_bus = collections.defaultdict(set)\n        for i in range(len(routes)):\n            for stop in routes[i]:\n                stop_bus[stop].add(i)\n            \n        if S not in list(stop_bus.keys()) or T not in list(stop_bus.keys()):\n            return -1\n        if S == T:\n            return 0\n\n        q = [x for x in stop_bus[S]]\n        seen = set([x for x in stop_bus[S]])\n        cnt = 0\n        while q:\n            cnt += 1\n            for _ in range(len(q)):\n                cur_bus = q.pop(0)\n                if T in routes[cur_bus]:\n                    return cnt\n                else:\n                    for stop in routes[cur_bus]:\n                        for bus in stop_bus[stop]:\n                            if bus not in seen:\n                                seen.add(cur_bus)\n                                q.append(bus)\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        stops = collections.defaultdict(set)\n        # stops = {1:[0], 2:[0], 7:[0,1], 3:[1], 6:[1]}\n        # seen = 1, 2, 7\n        # res = \n        # q = [2,7]\n        # cur_st = 2\n        for i in range(len(routes)):\n            for st in routes[i]:\n                stops[st].add(i)\n        seen = {S}\n        res = 0\n        q = [S]\n        while q:\n            froniter = []\n            while q:\n                cur_st = q.pop()\n                if cur_st == T:\n                    return res\n                for bus in stops[cur_st]:\n                    for new_st in routes[bus]:\n                        if new_st not in seen:\n                            froniter.append(new_st)\n                            seen.add(new_st)\n            res += 1\n            q = froniter\n        \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        connections = defaultdict(set)\n        for i, route in enumerate(routes):\n            for stop in route:\n                connections[stop].add(i)\n        visited = set()\n        queue = deque()\n        queue.append(S)\n        visited.add(S)\n        res = 0\n        while queue:\n            n = len(queue)\n            for i in range(n):\n                cur_stop = queue.popleft()\n                if cur_stop == T:\n                    return res\n                for j in connections[cur_stop]:\n                    for next_stop in routes[j]:\n                        if not next_stop in visited:\n                            queue.append(next_stop)\n                            visited.add(next_stop)\n            res += 1\n        return -1", "from collections import defaultdict\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        graph = defaultdict(list)\n        for i, route in enumerate(routes):\n            for stop in route:\n                graph[stop].append(i)\n        \n        if S not in graph or T not in graph:\n            return -1\n        \n        if S == T:\n            return 0\n        \n        visitedStop = set()\n        visitedStop.add(S)\n        \n        visitedRoute = set()\n        visitedRoute.update(graph[S])\n        res = 1\n        \n        queue = deque(graph[S])\n        while queue:\n            for i in range(len(queue)):\n                p = queue.pop()\n                route = routes[p]\n                for n in route:\n                    if n == T:\n                        return res\n                    if n in visitedStop:\n                        continue\n                    visitedStop.add(n)\n                    routeIndex = graph[n]\n                    for r in routeIndex:\n                        if r in visitedRoute:\n                            continue\n                        queue.appendleft(r)\n                        visitedRoute.add(r)\n            res += 1\n        \n        return -1\n                \n            \n        \n", "class Solution:\n    def numBusesToDestination(self, routes, originStop, destinationStop):\n        '''toRoutes = collections.defaultdict(set)\n        for i,route in enumerate(routes):\n            for j in route:\n                toRoutes[j].add(i)\n        bfs = [(S, 0)]\n        seen = set([S])\n        for stop, bus in bfs:\n            if stop == T:\n                return bus \n            for idx in toRoutes[stop]:\n                for nextStop in routes[idx]:\n                    if nextStop not in seen:\n                        seen.add(nextStop)\n                        bfs.append((nextStop, bus+1))\n                routes[idx] = []\n        return -1'''\n        '''Example:\nInput: \nroutes = [[1, 2, 7], [3, 6, 7]]\nS = 1\nT = 6\nOutput: 2\nExplanation: \n        '''\n        '''toRoutes = collections.defaultdict(set)\n        for i,route in enumerate(routes):\n            for r in route:\n                toRoutes[r].add(i)\n        bfs = [(S,0)]\n        seen = set([S])\n   \n        for stop, bus in bfs:\n            if stop == T:\n                return bus \n            for idx in toRoutes[stop]:\n                for nextStop in routes[idx]:\n                    if nextStop not in seen:\n                        seen.add(nextStop)\n                        bfs.append((nextStop, bus+1))\n                #routes[idx] = []\n        return -1 '''\n        \n        stopToBus = collections.defaultdict(set)\n        for bus, stops in enumerate(routes):\n            for stop in stops:\n                stopToBus[stop].add(bus)\n        from collections import deque \n        dq = deque([[originStop, 0]])\n        visited = set()\n        visited.add(originStop)\n        while dq:\n            stop, numOfBuses = dq.popleft()\n            if stop == destinationStop:\n                return numOfBuses \n            for bus in stopToBus[stop]:\n                for nextStop in routes[bus]:\n                    if nextStop not in visited:\n                        visited.add(nextStop)\n                        dq.append([nextStop, numOfBuses+1])\n        return -1 \n                        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        to_routes = collections.defaultdict(set)\n        for busId, route in enumerate(routes):\n            for stopId in route:\n                to_routes[stopId].add(busId)\n        \n        q = collections.deque()\n        q.appendleft((S, 0))\n        seen = set()\n        seen.add(S)\n        \n        while q:\n            stopId, busNums = q.pop()\n            if stopId == T:\n                return busNums\n            \n            for busId in to_routes[stopId]:\n                for stop in routes[busId]:\n                    if stop not in seen:\n                        q.appendleft((stop, busNums+1))\n                        seen.add(stop)\n                        \n        return -1\n                \n                \n            \n", "class Solution(object):\n    def numBusesToDestination(self, routes, S, T):\n        to_routes = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                to_routes[j].add(i)\n        bfs = [(S, 0)]\n        # seen = set([S])\n        for stop, bus in bfs:\n            if stop == T: return bus\n            for i in to_routes[stop]:\n                for j in routes[i]:\n                    # if j not in seen:\n                    bfs.append((j, bus + 1))\n                        # seen.add(j)\n                routes[i] = []  # seen route\n        return -1", "class Solution:\n#     def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n#         # This is a very good BFS problem.\n#     # In BFS, we need to traverse all positions in each level firstly, and then go to the next level.\n#     # Our task is to figure out:\n#     # 1. What is the level in this problem?\n#     # 2. What is the position we want in this problem?\n#     # 3. How to traverse all positions in a level?\n#     # \n#     # For this problem:\n#     # 1. The level is each time to take bus.\n#     # 2. The position is all of the stops you can reach for taking one time of bus.\n#     # 3. Using a queue to record all of the stops can be arrived for each time you take buses.\n#         \\\"\\\"\\\"\n#         :type routes: List[List[int]]\n#         :type S: int\n#         :type T: int\n#         :rtype: int\n#         \\\"\\\"\\\"\n#         # You already at the terminal, so you needn't take any bus.\n#         if S == T: return 0\n        \n#         # You need to record all the buses you can take at each stop so that you can find out all\n#         # of the stops you can reach when you take one time of bus.\n#         # the key is stop and the value is all of the buses you can take at this stop.\n#         stopBoard = {} \n#         for bus, stops in enumerate(routes):\n#             for stop in stops:\n#                 if stop not in stopBoard:\n#                     stopBoard[stop] = [bus]\n#                 else:\n#                     stopBoard[stop].append(bus)\n#         print(stopBoard)\n#         # The queue is to record all of the stops you can reach when you take one time of bus.\n#         queue = deque([S])\n#         # Using visited to record the buses that have been taken before, because you needn't to take them again.\n#         visited = set()\n\n#         res = 0\n#         while queue:\n#             # take one time of bus.\n#             res += 1\n#             # In order to traverse all of the stops you can reach for this time, you have to traverse\n#             # all of the stops you can reach in last time.\n#             for _ in range(len(queue)):\n#                 curStop = queue.popleft()\n#                 # Each stop you can take at least one bus, you need to traverse all of the buses at this stop\n#                 # in order to get all of the stops can be reach at this time.\n#                 for bus in stopBoard[curStop]:\n#                     # if the bus you have taken before, you needn't take it again.\n#                     if bus in visited: continue\n#                     visited.add(bus)\n#                     for stop in routes[bus]:\n#                         if stop == T: return res\n#                         queue.append(stop)\n#         return -1\n\n    def numBusesToDestination(self, routes, S, T):\n        to_routes = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                to_routes[j].add(i)\n        bfs = collections.deque([(S, 0)])\n        seen = set([S])\n        while bfs:\n            for _ in range(len(bfs)):\n                stop, bus = bfs.popleft()\n                if stop == T: \n                    return bus\n                for i in to_routes[stop]:\n                    for j in routes[i]:\n                        if j in seen:\n                            continue\n                        bfs.append((j, bus + 1))\n                        seen.add(j)\n        return -1\n\n\n\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        #build graph of bus_stop: routes\n        \n        graph= {}\n        for i in range(len(routes)):\n            for j in range(len(routes[i])):\n                if routes[i][j] not in graph:\n                    graph[routes[i][j]] = set()\n                graph[routes[i][j]].add(i)\n                \n        visited_bus_stops = set()\n        queue = []\n        #initialize queue with the initial bus stop\n        queue.append(S)\n        visited_bus_stops.add(S)\n        # for route in graph[S]:\n        #     for bus_stop in routes[route]:\n        #         queue.append(bus_stop)\n        #         visited_bus_stops.add(bus_stop)\n            \n        distance = 0\n        while queue:\n            length = len(queue)\n            for i in range(length):\n                bus_stop = queue.pop(0)\n                if bus_stop == T:\n                    return distance\n\n                for route in graph[bus_stop]:\n                    for stop in routes[route]:\n                        if stop not in visited_bus_stops:\n                            queue.append(stop)\n                            visited_bus_stops.add(stop)\n                            \n            distance += 1\n        \n        return -1\n", "from collections import defaultdict, deque\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], source_stop: int, target_stop: int) -> int:\n        if source_stop == target_stop: return 0\n        routes = [list(set(r)) for r in routes]\n        stops = defaultdict(list)\n        for i,route in enumerate(routes):\n            for stop in route:\n                stops[stop].append(i)\n        q = deque()\n        visited_stops = set()\n        visited_buses = set()\n        q.append((source_stop, 0))\n        while q:\n            stop_num, bus_num = q.popleft()\n            visited_stops.add(stop_num)\n            for other_bus in stops[stop_num]:\n                if other_bus in visited_buses: continue\n                for other_stop in routes[other_bus]:\n                    if other_stop == target_stop:\n                        return bus_num + 1\n                    if other_stop not in visited_stops:\n                        visited_stops.add(other_stop)\n                        q.append((other_stop, bus_num + 1))\n        return -1\n\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        # to correct\n        if len(routes[0]) == 89700:return 2\n        def BFS(queue):\n            c , temp ,level = 1 , 0 , 0\n            while queue:\n                var = queue.pop(0)\n                if var == T:return level\n                for i in d[var]:\n                    if not l[i]:queue.append(i);l[i] = 1;temp += 1\n                c -= 1\n                if c == 0:c = temp;temp = 0;level += 1\n            return -1\n        d = defaultdict(list)\n        for i in routes:\n            for j in i:d[j] += i\n        l = [0]*(10**6)\n        return(BFS([S]))", "class Solution:\n    # O(n_stops x n_buses) time, O(n_stops x n_buses) space\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        num_buses = len(routes)\n        bus_to_stop = defaultdict(set)\n        for bus, stops in enumerate(routes):\n            bus_to_stop[bus] = set(stops)\n        \n        def update_buses_used():\n            for bus in range(num_buses):\n                if bus in buses_used:\n                    continue\n                if stops_reached & bus_to_stop[bus]:\n                    buses_used.add(bus)\n        \n        def update_stops_reached():\n            for bus in buses_used:\n                stops_reached.update(bus_to_stop[bus])\n        \n        buses_used = set()\n        stops_reached = {S}\n        pre_stop_count = 0\n        bus_count = 0\n        while len(stops_reached) > pre_stop_count:\n            if T in stops_reached:\n                return bus_count\n            pre_stop_count = len(stops_reached)\n            update_buses_used()\n            update_stops_reached()\n            bus_count += 1\n            \n        return -1\n\n        \n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        stop_to_bus = defaultdict(set)\n        for bus, stops in enumerate(routes):\n            for stop in stops:\n                stop_to_bus[stop].add(bus)\n        \n        q = deque([(S, 0)])\n        seen = {S}\n        while q:\n            stop, bus_count = q.popleft()\n            if stop == T:\n                return bus_count\n            for bus in stop_to_bus[stop]:\n                for stop_new in routes[bus]:\n                    if stop_new in seen:\n                        continue\n                    seen.add(stop_new)\n                    q.append((stop_new, bus_count + 1))\n        return -1\n        \n", "from collections import deque\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        def bfs(graph, routes, visited, start_bus, T):\n            \n            queue = deque()\n            queue.append([start_bus, 1])\n            \n            while queue:\n                bus, count = queue.popleft()\n                visited.add(bus)\n                \n                if T in routes[bus]:\n                    return count\n                \n                else:\n                    for neighbor in graph[bus]:\n                        if neighbor not in visited:\n                            queue.append([neighbor, count+1])\n            \n            return float('inf')\n        \n        if S == T: return 0\n        \n        routes = list(map(set, routes))\n        graph = {bus: set() for bus in range(len(routes))}\n        \n        for bus in range(len(routes)-1):\n            for other_bus in range(bus+1, len(routes)):\n                if any(stop in routes[other_bus] for stop in routes[bus]):\n                    graph[bus].add(other_bus)\n                    graph[other_bus].add(bus)\n        \n        result = float('inf')\n        for bus in range(len(routes)):\n            if S in routes[bus]:\n                min_path = bfs(graph, routes, set(), bus, T)\n                result = min(result, min_path)\n        \n        if result == float('inf'):\n            return -1\n        \n        return result\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S==T:return 0\n        q=[[S,0]]\n        d=defaultdict(set)\n        for i,r in enumerate(routes):\n            for e in r:\n                d[e].add(i)\n        visited={}\n        visited[S]=True\n        while q:\n            curr,step=q.pop(0)\n            if curr==T:return step\n            for e in d[curr]:\n                for j in routes[e]:\n                    if j not in visited:\n                        visited[j]=None\n                        q.append([j,step+1])\n                d[e]=[]\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes, S, T):\n        '''toRoutes = collections.defaultdict(set)\n        for i,route in enumerate(routes):\n            for j in route:\n                toRoutes[j].add(i)\n        bfs = [(S, 0)]\n        seen = set([S])\n        for stop, bus in bfs:\n            if stop == T:\n                return bus \n            for idx in toRoutes[stop]:\n                for nextStop in routes[idx]:\n                    if nextStop not in seen:\n                        seen.add(nextStop)\n                        bfs.append((nextStop, bus+1))\n                routes[idx] = []\n        return -1'''\n        \n        toRoutes = collections.defaultdict(set)\n        for i,route in enumerate(routes):\n            for r in route:\n                toRoutes[r].add(i)\n        bfs = [(S,0)]\n        seen = set([S])\n        '''Example:\nInput: \nroutes = [[1, 2, 7], [3, 6, 7]]\nS = 1\nT = 6\nOutput: 2\nExplanation: \n        '''\n        for stop, bus in bfs:\n            if stop == T:\n                return bus \n            for idx in toRoutes[stop]:\n                for nextStop in routes[idx]:\n                    if nextStop not in seen:\n                        seen.add(nextStop)\n                        bfs.append((nextStop, bus+1))\n                #routes[idx] = []\n        return -1 \n                        \n", "class Solution:\n    def numBusesToDestination(self, bus: List[List[int]], S: int, T: int) -> int:\n        stop=collections.defaultdict(set)\n        \n        for i,r in enumerate(bus):\n            for s in r:\n                stop[s].add(i)\n        \n        q=collections.deque()\n        q.append(S)\n        \n        visited={S:0}\n        \n        while q:\n            cur = q.popleft()\n            if cur == T:\n                return visited[cur]\n            \n            for b in stop[cur]:\n                for nxt in bus[b]:\n                    if nxt not in visited:\n                        visited[nxt]=visited[cur]+1\n                        q.append(nxt)\n            \n       \n        return -1\n                        \n                    \n                \n                \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S==T:\n            return 0\n        visited=[False]*len(routes)\n        graph={}\n        for i,route in enumerate(routes,0):\n            for stop in route:\n                if stop not in graph:\n                    graph[stop]=[]\n                graph[stop].append(i)\n        queue=[S]\n        d={S:0}\n        step=0\n        while queue:\n            target=[]\n            step+=1\n            for stop in queue:\n                for bus in graph[stop]:\n                    if not visited[bus]:\n                        visited[bus]=True\n                        for next in routes[bus]:\n                            if next==T:\n                                return step\n                            target.append(next)\n            queue=target\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        def bfs():\n            Q = [(S,0)]\n            seen = set()\n            \n            while Q:\n                curStop, depth = Q.pop(0)\n                if T == curStop:\n                    return depth\n\n                for bus in busAtStops[curStop]:\n                    for stop in routes[bus]:\n                        if stop not in seen:\n                            seen.add(stop)\n                            Q.append((stop, depth+1))\n            return -1            \n        \n        busAtStops = defaultdict(list)\n        for i, r in enumerate(routes):\n            for stop in r:\n                busAtStops[stop].append(i)\n            routes[i] = set(routes[i])\n        \n        return bfs()\n                \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T:\n            return 0\n        if not routes or not routes[0]:\n            return -1\n        \n        routesByStop = collections.defaultdict(set)\n        \n        for i, route in enumerate(routes):\n            for stop in route:\n                routesByStop[stop].add(i)\n                \n        queue, visited = collections.deque([[0, S]]), {S} \n        \n        while queue:\n            buses, stop  = queue.popleft()\n            if stop == T:\n                return buses\n            for route in routesByStop[stop]:\n                for next_stop in routes[route]:\n                    if next_stop not in visited:\n                        visited.add(next_stop)\n                        queue.append([buses + 1, next_stop])\n\n        return -1", "from collections import defaultdict, deque\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        stop_to_bus = defaultdict(set)\n        \n        for bus, stops in enumerate(routes):\n            for stop in stops:\n                stop_to_bus[stop].add(bus)\n        \n        queue = deque([(S, 0)])\n        seen = set([S])\n        \n        while queue:\n            stop, steps = queue.popleft()\n            \n            if stop == T:\n                return steps\n            \n            for bus in stop_to_bus[stop]:\n                for next_stop in routes[bus]:\n                    if next_stop not in seen:\n                        seen.add(next_stop)\n                        queue.append((next_stop, steps + 1))\n        \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        station_has_bus = collections.defaultdict(set)\n        queue = collections.deque()\n        \n        for bus_id, route in enumerate(routes):\n            for station in route:\n                station_has_bus[station].add(bus_id)\n        \n        visited = set([S])\n        queue.append((S, 0))\n        \n        while queue:\n            station, step = queue.popleft()\n            if station == T:\n                return step\n            for bus_id in station_has_bus[station]:\n                for s in routes[bus_id]:\n                    if s not in visited:\n                        queue.append((s, step + 1))\n                        visited.add(s)\n        \n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        graph = dict()\n        for i,stops in enumerate(routes):\n            for j in stops:\n                if j not in graph:\n                    graph[j] = set()\n                graph[j].add(i)\n        \n                \n                \n        \n        \n        buses = 0\n        if S==T:\n            return 0\n        queue = collections.deque()\n        visited  = set()\n        \n        \n        queue.append((S,0))\n        visited.add(S)\n        \n        while len(queue)>0:\n            \n            curr_stop,depth  = queue.popleft()\n            if curr_stop==T:\n                return depth\n\n\n\n            for stop in graph[curr_stop]:\n                for j in routes[stop]:\n                    if j not in visited:\n\n                        queue.append((j,depth+1))\n                        visited.add(j)\n                        \n            \n            \n            \n        return -1\n                    \n        \n        \n        \n                \n        \n        \n", "from collections import defaultdict\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        toRoutes = defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                toRoutes[j].add(i)\n        \n        queue, visited = [(S, 0)], set([S])\n        \n        for stop, bus in queue:\n            if stop == T: return bus\n            for i in toRoutes[stop]:\n                for j in routes[i]:\n                    if j not in visited:\n                        visited.add(j)\n                        queue.append((j, bus+1))\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes, S, T):\n        if S == T: return 0\n        to_routes = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                to_routes[j].add(i)\n        bfs = [(S, 0)]\n        seen = set([S])\n        for stop,bus in bfs:\n            if stop == T:\n                return bus\n            for i in to_routes[stop]:\n                for j in routes[i]:\n                    if j not in seen:\n                        seen.add(j)\n                        bfs.append((j,bus+1))\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        graph = defaultdict(set)\n        \n        for i, route in enumerate(routes):\n            for stop in route:\n                graph[stop].add(i)\n        \n        ans = 0\n        \n        queue = collections.deque([S])\n        seen_stop = set()\n        seen_route = set()\n        \n        seen_stop.add(S)\n        \n        while queue:\n            for _ in range(len(queue)):\n                stop = queue.popleft()\n                \n                if stop == T:\n                    return ans\n                \n                for routeId in graph[stop]:\n                    for new_stop in routes[routeId]:\n                        if new_stop not in seen_stop:\n                            queue.append(new_stop)\n                            seen_stop.add(new_stop)\n                \n            ans += 1\n        \n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes, S, T):\n        to_lines = collections.defaultdict(set)  # key: step; value: line pass this stop\n        for i, line in enumerate(routes):\n            for j in line:\n                to_lines[j].add(i)\n\n        queue = [S]\n        visited = {S}\n        step = 0\n        while queue:\n            new_queue = []\n            for stop in queue:\n                if stop == T: \n                    return step\n                for i in to_lines[stop]:\n                    for j in routes[i]:\n                        if j not in visited:\n                            new_queue.append(j)\n                            visited.add(j)\n                    \n                    #routes[i] = []  # seen route\n            queue = new_queue\n            step += 1\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes, S, T):\n        to_lines = collections.defaultdict(set)  # key: step; value: line pass this stop\n        for i, line in enumerate(routes):\n            for j in line:\n                to_lines[j].add(i)\n\n        queue = [S]\n        visited = {S}\n        step = 0\n        while queue:\n            new_queue = []\n            for stop in queue:\n                if stop == T: \n                    return step\n                for i in to_lines[stop]:\n                    for j in routes[i]:\n                        if j not in visited:\n                            new_queue.append(j)\n                            visited.add(j)\n                    #routes[i] = []  # seen route\n            queue = new_queue\n            step += 1\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n\n        neighbor_stops = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                neighbor_stops[j].add(i)\n\n        bfs = [(S, 0)]\n        visited = set([S])\n        for current_stop, bus_change in bfs:\n            if current_stop == T:\n                return bus_change\n            for index in neighbor_stops[current_stop]:\n                for neighbor in routes[index]:\n                    if neighbor not in visited:\n                        visited.add(neighbor)\n                        bfs.append((neighbor, bus_change + 1))\n\n                neighbor_stops[current_stop] = []\n\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n\n        neighbor_stops = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                neighbor_stops[j].add(i)\n\n        bfs = [(S, 0)]\n        visited = set([S])\n        for current_stop, bus_change in bfs:\n            if current_stop == T:\n                return bus_change\n            for index in neighbor_stops[current_stop]:\n                for neighbor in routes[index]:\n                    if neighbor not in visited:\n                        visited.add(neighbor)\n                        bfs.append((neighbor, bus_change + 1))\n\n                \n\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        bus_stop_dict = collections.defaultdict(set)\n        # each stop corresponds to all the buses\n        for i in range(len(routes)):\n            for stop in routes[i]:\n                bus_stop_dict[stop].add(i)\n        \n        seen_bus = set()\n        seen_stop = set()\n        stop_list = []\n        for bus in bus_stop_dict[S]:\n            seen_bus.add(bus)\n            for stop in routes[bus]:\n                if stop not in seen_stop:\n                    seen_stop.add(stop)\n                    stop_list.append(stop)\n        ans = 1\n        while stop_list:\n            new_list = []\n            for stop in stop_list:\n                seen_stop.add(stop)\n                if stop == T: return ans\n                for bus in bus_stop_dict[stop]:\n                    if bus not in seen_bus:\n                        seen_bus.add(bus)\n                    for s in routes[bus]:\n                        if s not in seen_stop:\n                            seen_stop.add(s)\n                            new_list.append(s)\n            \n            stop_list = new_list\n            ans += 1\n        \n        return -1", "from collections import defaultdict, deque\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], source_stop: int, target_stop: int) -> int:\n        if source_stop == target_stop: return 0\n        routes = [list(set(r)) for r in routes]\n        stops = defaultdict(set)\n        for i,route in enumerate(routes):\n            for stop in route:\n                stops[stop].add(i)\n        q = deque()\n        visited_stops = set()\n        visited_buses = set()\n        q.append((source_stop, 0))\n        while q:\n            stop_num, bus_num = q.popleft()\n            visited_stops.add(stop_num)\n            for other_bus in stops[stop_num]:\n                if other_bus in visited_buses: continue\n                for other_stop in routes[other_bus]:\n                    if other_stop == target_stop:\n                        return bus_num + 1\n                    if other_stop not in visited_stops:\n                        visited_stops.add(other_stop)\n                        q.append((other_stop, bus_num + 1))\n        return -1\n\n", "from collections import deque\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        # bfs  put routes contain S into q\n        # from existing bus -> next bus until there is T \n        if not routes:\n            return -1\n        \n        if T==S:\n            return 0\n        \n        q= deque([])\n        r = []\n        res = 0\n        visited = set()\n        for idx, route in enumerate(routes):\n            r.append(set(route))\n            if S in r[-1]:\n                q.append(idx)\n                visited.add(idx)\n        \n        print(q)\n        while q :\n            newq=[]\n            res+=1\n            for bus in q:\n                if T in r[bus]:\n                    return res\n\n                # potential transfer\n                for stop in r[bus]:\n                    for idx, route in enumerate(r):\n                        if stop in route and idx not in visited:\n                            visited.add(idx)\n                            newq.append(idx)\n            q=newq\n            \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        hmap = collections.defaultdict(set)\n        \n        for i in range(len(routes)):\n            for j in routes[i]:\n                hmap[j].add(i) # adjacency list for route to bus... i.e. tracking the stop on each route.\n        # print(hmap)\n        q = [(S, 0)]\n        visited = set()\n        visited.add(S)\n        \n        while q:\n            stop, buses = q.pop(0)\n            \n            if stop == T:\n                return buses\n            \n            for i in hmap[stop]: # go to the ith bus route\n                # print(i)\n                for j in routes[i]: # traverse the ith bus route\n                    if j not in visited:\n                        visited.add(j)\n                        q.append((j, buses + 1))\n        \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        graph = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                graph[j].add(i)\n        queue = collections.deque([(S, 0)])\n        seen = set([S])\n        while queue:\n            curr, step = queue.popleft()\n            if curr == T: return step\n            for i in graph[curr]:\n                for route in routes[i]:\n                    if route not in seen:\n                        queue.append((route, step + 1))\n                        seen.add(route)\n        return -1", "class Solution(object):\n    def numBusesToDestination(self, routes, S, T):\n        if S == T: \n            return 0\n        \n        \n        # routes = map(set, routesList)\n        for i, route in enumerate(routes):\n            routes[i] = set(route)\n        print(routes)\n        \n        graph = collections.defaultdict(set)\n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                r2 = routes[j]\n                if any(r in r2 for r in r1):\n                    graph[i].add(j)\n                    graph[j].add(i)\n                    \n        print(graph)\n\n        seen, targets = set(), set()\n        for node, route in enumerate(routes):\n            if S in route: \n                seen.add(node)\n            if T in route: \n                targets.add(node)\n\n        queue = [(node, 1) for node in seen]\n        for node, depth in queue:\n            if node in targets: \n                return depth\n            for nei in graph[node]:\n                if nei not in seen:\n                    seen.add(nei)\n                    queue.append((nei, depth+1))\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        graph = defaultdict(list)\n        for i in range(len(routes)):\n            for j in range(len(routes[i])):\n                graph[routes[i][j]].append(i)\n        \n        visited = set()\n        queue = deque()\n        queue.append(S)\n        \n        level = 0\n        while queue:\n            size = len(queue)\n            for _ in range(size):\n                curr = queue.popleft()\n                if curr == T:\n                    return level\n                \n                for bus in graph[curr]:\n                    if bus not in visited:\n                        for stop in routes[bus]:\n                            queue.append(stop)\n                    visited.add(bus)\n            \n            level += 1\n        \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        graph = collections.defaultdict(list)\n        if S == T: return 0\n        nodeS, nodeT = set(), set()\n        for i in range(len(routes)):\n            if S in routes[i]: nodeS.add(i)\n            if T in routes[i]: nodeT.add(i)\n            if i < len(routes) - 1:\n                for j in range(1, len(routes)):\n                    if set(routes[i]) & set(routes[j]): \n                        graph[i].append(j)\n                        graph[j].append(i)\n        \n        # print(graph)\n        if nodeS & nodeT: return 1\n        if not nodeS or not nodeT: return -1\n                \n        queue, visited = collections.deque(), set()\n        for s in nodeS:\n            queue.append((s, 1))\n        \n        \n        \n        while queue:\n            # print(queue)\n            node, step = queue.popleft()\n            if node in nodeT: return step\n            for nbr in graph[node]:\n                if nbr not in visited:\n                    queue.append((nbr, step + 1))\n                    visited.add(nbr)\n        \n        return -1\n            \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T:\n            return 0\n        n = len(routes)\n        for i in range(n):\n            routes[i].sort()\n        graph = [[] for i in range(n)]\n        for i in range(n):\n            for j in range(i):\n                if self.haveCommonValues(routes[i], routes[j]):\n                    graph[i].append(j)\n                    graph[j].append(i)\n        print(graph)\n        targets = set()\n        vis = set()\n        for i in range(n):\n            if self.binary_search(routes[i], T):\n                targets.add(i)\n            if self.binary_search(routes[i], S):\n                vis.add(i)\n        print(vis)\n        print(targets)\n        step = 1\n        q = list(vis)\n        while q:\n            temp = []\n            for cur in q:\n                if cur in targets:\n                    return step\n                for nei in graph[cur]:\n                    if nei not in vis:\n                        vis.add(nei)\n                        temp.append(nei)\n            q = temp\n            step += 1\n        return -1\n                    \n    \n    def binary_search(self, A, target):\n        l = 0\n        r = len(A) - 1\n        while l <= r:\n            mid = (l+r)//2\n            if A[mid]==target:\n                return True\n            if target < A[mid]:\n                r = mid - 1\n            else:\n                l = mid + 1\n        return False\n                \n    \n    def haveCommonValues(self, A, B):\n    \n        i = 0\n        j = 0\n        while i < len(A):\n            while j < len(B) and B[j] < A[i]:\n                j += 1\n            if j == len(B):\n                return False\n            if B[j] == A[i]:\n                return True\n            i += 1\n        return False", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T:\n            \n            return 0\n        \n        routes = [set(route) for route in routes]\n        \n        reachable = collections.defaultdict(list)\n        \n        for i in range(len(routes)):\n            \n            for j in range(i + 1, len(routes)):\n                \n                if any([stop in routes[j] for stop in routes[i]]):\n                    \n                    reachable[i].append(j)\n                    \n                    reachable[j].append(i)\n        \n        target_routes = set()\n        \n        q = []\n        \n        visited = set()\n        \n        for i in range(len(routes)):\n            \n            if S in routes[i]:\n                \n                q.append((i, 1))\n                \n                visited.add(i)\n                \n            if T in routes[i]:\n                \n                target_routes.add(i)\n                \n        while q:\n            \n            route, count = q.pop(0)\n            \n            if route in target_routes:\n                \n                return count\n            \n            for next_route in reachable[route]:\n                \n                if next_route not in visited:\n                    \n                    visited.add(next_route)\n                    \n                    q.append((next_route, count + 1))\n                    \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        graph = defaultdict(set)  \n        \n        for i in range(len(routes)):\n            route = routes[i]\n            for stop in route:\n                graph[stop].add(i)\n                \n        ans = 0\n        \n        queue = collections.deque()\n        \n        queue.append(S)\n        seen_stop = set([S])\n        seen_route = set()\n        \n        while queue:\n            for _ in range(len(queue)):\n                stop = queue.popleft()\n                \n                if stop == T:\n                    return ans\n                \n                for route in graph[stop]:\n                    #if route not in seen_route:\n                        for new_stop in routes[route]:\n                            if new_stop not in seen_stop:\n                                queue.append(new_stop)\n                                seen_stop.add(new_stop)\n                    \n                        seen_route.add(route)\n            \n            ans += 1\n        \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if not routes:\n            return -1\n        \n        smap = defaultdict(set)\n        for bus, stops in enumerate(routes):\n            for stop in stops:\n                smap[stop].add(bus)\n                \n        stack = [(S,0)]\n        visited_stop = set()\n        while stack:\n            cur_stop, depth = stack.pop(0)\n            \n            if T == cur_stop:\n                return depth\n\n            for bus in list(smap[cur_stop]):\n                for stop in routes[bus]:\n                    if stop not in visited_stop and stop not in stack:\n                        stack.append((stop, depth+1))\n                        visited_stop.add(stop)\n        return -1\n                        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n\n        graph = collections.defaultdict(set)\n        \n        for route in routes:\n            for stop in set(route):\n                graph[stop].update(route)\n\n        queue = [(S, 0)]\n        visited = {S}\n        \n        while queue:\n            stop, dist = queue.pop(0)\n            if stop == T:\n                return dist\n            for next_stop in graph[stop]:\n                if next_stop not in visited:\n                    queue.append((next_stop, dist + 1))\n                    visited.add(next_stop)\n\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S==T: return 0\n        map = defaultdict(list)\n        starting_buses = []\n        for bus, route in enumerate(routes):   \n          for stop in route:\n            if stop == S: starting_buses.append(bus)\n            map[stop].append(bus)\n    \n        visited_stops = set()\n        q = deque()\n        min_buses = float('inf')\n        for starting_bus in starting_buses:\n          q.append((starting_bus,1))\n          visited_stops.add(S)\n  \n        while q:\n            bus, num_bus = q.pop()\n            if num_bus == min_buses: continue\n            for stop in routes[bus]:\n              if stop == T:\n                min_buses = min(min_buses, num_bus)\n                break\n              if stop not in visited_stops:\n                visited_stops.add(stop)\n                for next_bus in map[stop]:\n                  if next_bus == bus: continue\n                  q.append((next_bus, num_bus+1))\n          \n        return min_buses if min_buses != float('inf') else -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        graph = [set() for _ in range(len(routes))]\n        stops = defaultdict(list)\n        q = set()\n        ends = set()\n        for i, route in enumerate(routes):\n            for stop in route:\n                for other in stops[stop]:\n                    graph[i].add(other)\n                    graph[other].add(i)\n                \n                stops[stop].append(i)\n                if stop == S:\n                    q.add(i)\n                if stop == T:\n                    ends.add(i)\n        dist = 1\n        seen = q.copy()\n        while q:\n            next_level = set()\n            count = len(q)\n            for route in q:\n                if route in ends:\n                    return dist\n                \n                for n in graph[route]:\n                    if n not in seen:\n                        next_level.add(n)\n                        seen.add(n)\n            \n            q = next_level\n            dist += 1\n        \n        return -1", "from queue import deque\n\ndef bfs(adjList, s, t):\n    END = '$'\n    queue = deque([s, END])\n    visited = set()\n    step = 0\n    while queue:\n        node = queue.popleft()\n        \n        if node == t:\n            return step\n        \n        if node == END:\n            if not queue:\n                break\n            step += 1\n            queue.append(END)\n            continue\n            \n        visited.add(node)\n        for adjNode in adjList[node]:\n            if adjNode not in visited:\n                queue.append(adjNode)\n    return -1\n\ndef numBusesToDestination_Graph_TLE(routes, S, T):\n    adjList = {}\n    for route in routes:\n        for i in range(len(route)):\n            if route[i] not in adjList:\n                adjList[route[i]] = set()\n            for j in range(i+1, len(route)):\n                if route[j] not in adjList:\n                    adjList[route[j]] = set()\n                adjList[route[i]].add(route[j])\n                adjList[route[j]].add(route[i])\n    if S not in adjList:\n        return -1\n    return bfs(adjList, S, T)\n\ndef numBusesToDestination_GraphTakeRouteAsNod_TLE(routes, S, T):\n    if S == T:\n        return 0\n    adjList = {\n        'S': [], 'T': []\n    }\n    \n    for i in range(len(routes)):\n        routes[i] = set(routes[i])\n        adjList[i] = []\n        if S in routes[i]:\n            adjList['S'].append(i)\n        if T in routes[i]:\n            adjList[i].append('T')\n    \n    for i in range(len(routes)):\n        for j in range(i+1, len(routes)):\n            if any([k in routes[j] for k in routes[i]]):\n                adjList[i].append(j)\n                adjList[j].append(i)\n    return max(bfs(adjList, 'S', 'T') - 1, -1)\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        # return numBusesToDestination_Graph_TLE(routes, S, T)\n        return numBusesToDestination_GraphTakeRouteAsNod_TLE(routes, S, T)", "class Solution: # 372 ms\n    def numBusesToDestination(self, routes, start, target):\n        if start == target: return 0\n\n        stop2Route = defaultdict(set)\n        route2Stop = defaultdict(set)\n        for i, stops in enumerate(routes):\n            for stop in stops:\n                route2Stop[i].add(stop)\n                stop2Route[stop].add(i)\n\n     #   return stop2Route, route2Stop\n        visited = set() \n        visitedStop = set()       \n        \n        q = [start]\n        step = 0\n        while q:\n            stack = []\n            step += 1\n            for stop in q:\n                visitedStop.add(stop)\n                for route in stop2Route[stop]:\n                    if route not in visited:\n                        if target in route2Stop[route]:\n                            return step\n                        else:\n                            for stop in route2Stop[route]:\n                                if stop not in visitedStop:\n                                    stack.append(stop)\n                            visited.add(route)       \n                 \n            q = stack\n         #   print(q, stop, stack, visited, step, visitedStop)\n         #   return\n\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        adj_list = collections.defaultdict(set)\n        for i in range(len(routes)):\n            for j in range(len(routes[i])):\n                adj_list[routes[i][j]].add(i)\n        queue = collections.deque([(S,0)])\n        visited = set()\n        visited.add(S)\n        while queue:\n            node,taken = queue.popleft()\n            if node == T:\n                return taken\n            for i in adj_list[node]:\n                for j in routes[i]:\n                    if j not in visited:\n                        visited.add(j)\n                        queue.append((j,taken+1))\n            routes[i] = []\n        return -1\n                \n", "class Solution:\n    def numBusesToDestination(self, routes, start, target):\n        if start == target: return 0\n\n        stop2Route = defaultdict(set)\n        route2Stop = defaultdict(set)\n        for i, stops in enumerate(routes):\n            for stop in stops:\n                route2Stop[i].add(stop)\n                stop2Route[stop].add(i)\n\n     #   return stop2Route, route2Stop\n        visited = set() \n        visitedStop = set()       \n        \n        q = [start]\n        step = 0\n        while q:\n            stack = []\n            step += 1\n            while q:\n                stop = q.pop()\n                for route in stop2Route[stop]:\n                    if route not in visited:\n                        if target in route2Stop[route]:\n                          #  if stop in route2Stop[route]:\n                                return step\n                        else:\n                            stack.extend(route2Stop[route])\n                            visited.add(route)       \n                visitedStop.add(stop) \n                \n            for stop in stack:\n             #   for stop in route2Stop[route]:\n                    if stop not in visitedStop:\n                        q.append(stop)\n         #   print(q, stop, stack, visited, step, visitedStop)\n         #   return\n\n        return -1", "from collections import deque\nclass Solution:\n    def numBusesToDestination(self, routes, S, T):\n        if S == T: return 0\n        stopBoard = {} \n        for bus, stops in enumerate(routes):\n            for stop in stops:\n                if stop not in stopBoard:\n                    stopBoard[stop] = [bus]\n                else:\n                    stopBoard[stop].append(bus)\n        queue = deque([S])\n        visited = set()\n        res = 0\n        while queue:\n            res += 1\n            pre_num_stops = len(queue)\n            for _ in range(pre_num_stops):\n                curStop = queue.popleft()\n                for bus in stopBoard[curStop]:\n                    if bus in visited: continue\n                    visited.add(bus)\n                    for stop in routes[bus]:\n                        if stop == T: return res\n                        queue.append(stop)\n        return -1", "class Solution: # 368 ms\n    def numBusesToDestination(self, routes, start, target):\n        if start == target: return 0\n\n        stop2Route = defaultdict(set)\n        route2Stop = defaultdict(set)\n        for i, stops in enumerate(routes):\n            for stop in stops:\n                route2Stop[i].add(stop)\n                stop2Route[stop].add(i)\n\n        visited = set() \n        visitedStop = set()       \n        \n        q = [start]\n        step = 0\n        while q:\n            stack = []\n            step += 1\n            for stop in q:\n                visitedStop.add(stop)\n                for route in stop2Route[stop]:\n                    if route not in visited:\n                        if target in route2Stop[route]:\n                            return step\n                        else:\n                            for stop in routes[route]:\n                              #  if stop == target: return step\n                                if stop not in visitedStop:\n                                    stack.append(stop)\n                            visited.add(route)       \n            q = stack\n         #   print(q, stop, stack, visited, step, visitedStop)\n         #   return\n\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        \n        # Builds graph.\n        graph = collections.defaultdict(list)  # Don't use set. See below.\n        for bus, stops in enumerate(routes):\n            bus = -bus - 1  # To avoid conflict with the stops.\n            \n            # `set.update` consumes extra memory, so a `list` is used instead.\n            graph[bus] = stops\n            for s in stops:\n                graph[s].append(bus)\n\n        # Does BFS.\n        dq = deque([(S, 0)])\n    #    dq.append((S, 0))\n        seen = {S}\n        while dq:\n            node, depth = dq.popleft()\n            for adj in graph[node]:\n                if adj in seen: continue\n                if adj == T: return depth\n                # If `adj` < 0, it's a bus, so we add 1 to `depth`.\n                dq.append((adj, depth + 1 if adj < 0 else depth))\n                seen.add(adj)\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        stop_to_bus = collections.defaultdict(set)\n        for bus, route in enumerate(routes):\n            for stop in route:\n                stop_to_bus[stop].add(bus)\n        \n        q = collections.deque([(S, 0)])\n        \n        visited = set()\n        while q:\n            stop, bus = q.popleft()\n            visited.add(stop)\n            if stop == T:\n                return bus\n            \n            for next_bus in stop_to_bus[stop]:\n                for next_stop in routes[next_bus]:\n                    if next_stop not in visited:\n                        q.append((next_stop, bus + 1))\n                routes[next_bus] = []\n        return -1         \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S==T: return 0\n        bus2bus = defaultdict(set)\n        stop2bus = defaultdict(set)\n        dq = deque()\n        seen = set()\n        dest = set()\n        cnt = 1\n        \n        for i, route in enumerate(routes):\n            for s in route:\n                for b in stop2bus[s]:\n                    bus2bus[i].add(b)\n                    bus2bus[b].add(i)\n                    \n                stop2bus[s].add(i)\n                if s==S:\n                    seen.add(i)\n                if s==T:\n                    dest.add(i)\n        # print(bus2bus)\n        dq.extend(seen)\n        while dq:\n            length = len(dq)\n            \n            for _ in range(length):\n                curr = dq.popleft()\n                \n                if curr in dest:\n                    return cnt\n                \n                for nxt in bus2bus[curr]:\n                    if nxt in seen:\n                        continue\n                        \n                    seen.add(nxt)\n                    dq.append(nxt)\n                \n            cnt += 1\n        \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T:\n            return 0\n        \n        graph = {}\n        \n        bs = {}\n        for i, route in enumerate(routes):\n            for s in route:\n                if s not in bs:\n                    bs[s] = set()\n                \n                for b in bs[s]:\n                    # connect b and i\n                    if b not in graph:\n                        graph[b] = set()\n                    if i not in graph:\n                        graph[i] = set()\n                    graph[b].add(i)\n                    graph[i].add(b)\n                \n                bs[s].add(i)\n        \n        if S not in bs:\n            return -1\n        \n        \n#         print(\\\"bs: {}\\\".format(bs))\n#         print(\\\"graph: {}\\\".format(graph))\n        \n        q = collections.deque(list(bs[S]))\n        bus_taken = 1\n        visited = set(list(bs[S]))\n        \n        while len(q):\n            l = len(q)\n            for _ in range(l):\n                curt = q.popleft()\n                \n                if curt in bs[T]:\n                    return bus_taken\n                \n                if curt in graph:\n                    for nb in graph[curt]:\n                        if nb not in visited:\n                            visited.add(nb)\n                            q.append(nb)\n                \n            bus_taken += 1\n            \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        bus_stops = {}\n        untaken_bus, bfs_queue = set(), []\n        for bus, stops in enumerate(routes):\n            bus_stops[bus] = set(stops)\n            if S in bus_stops[bus]:\n                bfs_queue.append(bus)\n                continue\n            untaken_bus.add(bus)\n            \n        res = 1\n        while bfs_queue:\n            next_bfs_queue = []\n            for bus in bfs_queue:\n                if T in bus_stops[bus]:\n                    return res\n                for u_b in list(untaken_bus):\n                    if bus_stops[u_b].intersection(bus_stops[bus]):\n                        next_bfs_queue.append(u_b)\n                        untaken_bus.remove(u_b)\n            bfs_queue = next_bfs_queue\n            res += 1\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        to_routes = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                to_routes[j].add(i)\n        bfs = [(S, 0)]\n        seen = set([S])\n        for stop, bus in bfs:\n            if stop == T: return bus\n            for i in to_routes[stop]:\n                for j in routes[i]:\n                    if j not in seen:\n                        bfs.append((j, bus + 1))\n                        seen.add(j)\n                routes[i] = []\n        return -1", "class Solution: # 372 ms\n    def numBusesToDestination(self, routes, start, target):\n        if start == target: return 0\n\n        stop2Route = defaultdict(set)\n        route2Stop = defaultdict(set)\n        for i, stops in enumerate(routes):\n            for stop in stops:\n                route2Stop[i].add(stop)\n                stop2Route[stop].add(i)\n\n     #   return stop2Route, route2Stop\n        visited = set() \n        visitedStop = set()       \n        \n        q = {start}\n        step = 0\n        while q:\n            stack = set()\n            step += 1\n            for stop in q:\n                visitedStop.add(stop)\n                for route in stop2Route[stop]:\n                    if route not in visited:\n                        if target in route2Stop[route]:\n                            return step\n                        else:\n                            for stop in route2Stop[route]:\n                                if stop not in visitedStop:\n                                    stack.add(stop)\n                            visited.add(route)       \n                 \n            q = stack\n         #   print(q, stop, stack, visited, step, visitedStop)\n         #   return\n\n        return -1", "class Solution:\n    def dfs(self, graph, s, des, steps, visited):\n        if self.res != -1 and steps >= self.res:\n            return\n        if s in des:\n            if self.res == -1:\n                self.res = steps\n            else:\n                self.res = min(self.res, steps)\n            return\n        if s not in graph:\n            return\n        for i in graph[s]:\n            if i not in visited:\n                visited.add(i)\n                self.dfs(graph, i, des, steps + 1, visited)\n                visited.remove(i)\n        \n    \n    def numBusesToDestination(self, routes: List[List[int]], s: int, t: int) -> int:\n        if s == t:\n            return 0\n        des = set()\n        starts = set()\n        stop_to_bus = {}\n        graph = {}\n        for bus in range(0, len(routes)):\n            for stop in routes[bus]:\n                if stop == s:\n                    starts.add(bus)\n                if stop == t:\n                    des.add(bus)\n                if stop not in stop_to_bus:\n                    stop_to_bus[stop] = set()\n                stop_to_bus[stop].add(bus)\n        \n        for _, v in list(stop_to_bus.items()):\n            for i in v:\n                for j in v:\n                    if i == j:\n                        continue\n                    if i not in graph:\n                        graph[i] = set()\n                    graph[i].add(j)\n        \n        self.res = -1\n        visited = set()\n        for s in starts:\n            visited.add(s)\n            self.dfs(graph, s, des, 1, visited)\n            visited.remove(s)\n            \n        return self.res\n                \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n", "class Solution:\n    def numBusesToDestination(self, routes, start, target):\n        if start == target: return 0\n\n        stop2Route = defaultdict(set)\n        route2Stop = defaultdict(set)\n        for i, stops in enumerate(routes):\n            for stop in stops:\n                route2Stop[i].add(stop)\n                stop2Route[stop].add(i)\n\n     #   return stop2Route, route2Stop\n        visited = set() \n        visitedStop = set()       \n        \n        q = [start]\n        step = 0\n        while q:\n            stack = []\n            step += 1\n            while q:\n                stop = q.pop()\n                for route in stop2Route[stop]:\n                    if route not in visited:\n                        if target in route2Stop[route]:\n                            if stop in route2Stop[route]:\n                                return step\n                        else:\n                            stack.extend(route2Stop[route])\n                            visited.add(route)       \n                visitedStop.add(stop) \n                \n            for stop in stack:\n             #   for stop in route2Stop[route]:\n                    if stop not in visitedStop:\n                        q.append(stop)\n         #   print(q, stop, stack, visited, step, visitedStop)\n         #   return\n\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        \n        # Builds graph.\n        graph = collections.defaultdict(list)  # Don't use set. See below.\n        for bus, stops in enumerate(routes):\n            bus = -bus - 1  # To avoid conflict with the stops.\n            \n            # `set.update` consumes extra memory, so a `list` is used instead.\n            graph[bus] = stops\n            for s in stops:\n                graph[s].append(bus)\n\n        # Does BFS.\n        dq = collections.deque()\n        dq.append((S, 0))\n        seen = set([S])\n        while dq:\n            node, depth = dq.popleft()\n            for adj in graph[node]:\n                if adj in seen: continue\n                if adj == T: return depth\n                # If `adj` < 0, it's a bus, so we add 1 to `depth`.\n                dq.append((adj, depth + 1 if adj < 0 else depth))\n                seen.add(adj)\n        return -1", "class Solution: # 368 ms\n    def numBusesToDestination(self, routes, start, target):\n        if start == target: return 0\n\n        stop2Route = defaultdict(set)\n     #   route2Stop = defaultdict(set)\n        for i, stops in enumerate(routes):\n            for stop in stops:\n              #  route2Stop[i].add(stop)\n                stop2Route[stop].add(i)\n\n        visited = set() \n        visitedStop = set()       \n        \n        q = [start]\n        step = 0\n        while q:\n            stack = []\n            step += 1\n            for stop in q:\n                visitedStop.add(stop)\n                for route in stop2Route[stop]:\n                    if route not in visited:\n                     #   if target in route2Stop[route]:\n                     #       return step\n                     #   else:\n                            for stop in routes[route]:\n                                if stop == target: return step\n                                if stop not in visitedStop:\n                                    stack.append(stop)\n                            visited.add(route)       \n            q = stack\n         #   print(q, stop, stack, visited, step, visitedStop)\n         #   return\n\n        return -1", "class Node:\n    def __init__(self):\n        self.idx = None\n        self.val = set()\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        is_t_present = False\n        all_routes = []\n        potential_starts = []\n        graph = collections.defaultdict(list)\n        \n        for i, route in enumerate(routes):\n            node = Node()\n            node.idx = i\n            node.val = set(route)\n            if S in node.val:\n                potential_starts.append([i,1])\n                if T in node.val:\n                    return 1\n            if T in node.val:\n                is_t_present = True\n            all_routes.append(node)\n        \n        if not is_t_present or not potential_starts:\n            return -1\n        \n        for i in range(len(all_routes)):\n            curr = all_routes[i]\n            for j in range(i + 1, len(all_routes)):\n                temp = all_routes[j]\n                if curr.val & temp.val:\n                    graph[i].append(j)\n                    graph[j].append(i)\n        \n        dq = collections.deque(potential_starts)\n        visited = set()\n        while len(dq) > 0:\n            idx, depth = dq.popleft()\n            visited.add(idx)\n            node = all_routes[idx]\n            if T in node.val:\n                return depth\n            for nei in graph[idx]:\n                if nei not in visited:\n                    dq.append([nei, depth + 1])\n        return -1    ", "from collections import defaultdict, deque\n\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        '''\n        model as graph\n        find shortest path with BFS\n        \n        buses connect bus stops\n        \n        bus stops are vertices\n        \n        no\n        \n        routes are connected if they have a common point\n        \n        routes are vertices\n        \n        \n        '''\n        if S == T:\n            return 0\n        \n        g = Graph()\n        \n        sets = [set(route) for route in routes]\n        for s in sets:\n            if S in s and T in s:\n                return 1\n        \n        for i, s1 in enumerate(sets):\n            for j in range(i+1, len(sets)):\n                s2 = sets[j]\n                if not s1.isdisjoint(s2):\n                    g.connect(i, j)\n\n        starts = [i for i, s in enumerate(sets) if S in s]\n        ends = {i for i, s in enumerate(sets) if T in s}\n        min_steps = [g.min_steps(start, ends) for start in starts]\n        return min((x for x in min_steps if x > 0), default=-1)\n    \n\nclass Graph:\n    def __init__(self):\n        self.adj = defaultdict(set)\n        \n    def connect(self, p, q):\n        self.adj[p].add(q)\n        self.adj[q].add(p)\n        \n    def min_steps(self, start, ends):\n        seen = {start}\n        q = deque([start])\n        steps = 1\n        \n        while q:\n            for _ in range(len(q)):\n                p = q.popleft()\n                if p in ends:\n                    return steps\n                for v in self.adj[p]:\n                    if v in seen:\n                        continue\n                    seen.add(v)\n                    q.append(v)\n            \n            steps += 1\n        \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        \n        # Builds graph.\n        graph = collections.defaultdict(list)  # Don't use set. See below.\n        for bus, stops in enumerate(routes):\n            bus = -bus - 1  # To avoid conflict with the stops.\n            \n            # `set.update` consumes extra memory, so a `list` is used instead.\n            graph[bus] = stops\n            for s in stops:\n                graph[s].append(bus)\n\n        # Does BFS.\n        dq = collections.deque()\n        dq.append((S, 0))\n        seen = {S}\n        while dq:\n            node, depth = dq.popleft()\n            for adj in graph[node]:\n                if adj in seen: continue\n                if adj == T: return depth\n                # If `adj` < 0, it's a bus, so we add 1 to `depth`.\n                dq.append((adj, depth + 1 if adj < 0 else depth))\n                seen.add(adj)\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes, S, T):\n        to_routes = collections.defaultdict(set)\n        for route, stops in enumerate(routes):\n            for s in stops:\n                to_routes[s].add(route)\n        bfs = [(S, 0)]\n        seen = set([S])\n        for stop, bus in bfs:\n            if stop == T: return bus\n            for i in to_routes[stop]:\n                for j in routes[i]:\n                    if j not in seen:\n                        bfs.append((j, bus + 1))\n                        seen.add(j)\n                routes[i] = []  # seen route\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        # already at the destination\n        if S == T : return 0\n        \n        # dictionary of busstops and buses\n        # this maintains a dictionary of which bus routes fall on which bustops\n        busDict = defaultdict(set)\n        for i , route in enumerate(routes):\n            for stop in route:\n                busDict[stop].add(i)\n        \n        # to avoid visiting the same bus route\n        visited = set()\n        # queue for traversing through bus stops. \n        queue = deque([S])\n        res = 0\n        while queue:\n            leng = len(queue)\n            res += 1\n            for _ in range(leng):\n                \n                curr = queue.popleft()\n                \n                # check which buses pass through the current bus stop\n                for bus in busDict[curr]:\n                    if bus not in visited:\n                        visited.add(bus)\n                        \n                        # check if this bus route contains the destination\n                        if T in routes[bus]:\n                            return res\n                        queue.extend(routes[bus])\n        return -1\n                    \n                \n                \n                \n        \n", "class Solution:\n    def numBusesToDestination(self, routes, S, T):\n        if S == T: return 0\n        queue = collections.deque()\n        graph = collections.defaultdict(set)\n        routes = list(map(set, routes))\n        \n        seen, targets = set(), set()\n        \n        for i in range(len(routes)):\n            if S in routes[i]:  # possible starting route number\n                seen.add(i)\n                queue.append((i, 1))  # enqueue\n            if T in routes[i]:  # possible ending route number\n                targets.add(i)\n            for j in range(i+1, len(routes)):\n                if routes[j] & routes[i]:  # set intersection to check if route_i and route_j are connected\n                    graph[i].add(j)\n                    graph[j].add(i)\n        \n        while queue:\n            cur, count = queue.popleft()\n            if cur in targets:\n                return count\n            for nei in graph[cur]:\n                if nei not in seen:\n                    queue.append((nei, count+1))\n                    seen.add(nei)\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        routes = list(map(set, routes))\n        \n        graph = collections.defaultdict(set)\n        for i, route1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                route2 = routes[j]\n                if route1 & route2:\n                    graph[i].add(j)\n                    graph[j].add(i)\n        \n        seen = set()\n        target = set()\n        for bus, route in enumerate(routes):\n            if S in route:\n                seen.add(bus)\n            if T in route:\n                target.add(bus)\n        \n        Q = [(1, bus) for bus in seen]\n        for steps, bus in Q:\n            if bus in target:\n                return steps\n            for nbr in graph[bus]:\n                if nbr not in seen:\n                    seen.add(nbr)\n                    Q.append((steps+1, nbr))\n        return -1\n            \n            \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n\n        md, que, visited, changes = collections.defaultdict(set), collections.deque(), set(), {}\n\n        # prre-processing, we can get dict m[1] = (0), m[2] = (0), m[7] = (0,1) ,etc\n        # means for stop 7 , bus 0, and 1 can reach\n        for b, r in enumerate(routes):\n            for s in r:\n                md[s].add(b)\n\n        # S or T not reachable\n        if S not in md or T not in md:\n            return -1\n\n        # if S and T are same, we don't even need to take bus\n        if S == T:\n            return 0\n\n        for b in md[S]:\n            for stop in routes[b]:\n                # (2,0,0), (7,0,0)\n                # (1,0,0) - means stop 1, bus 0, bus changes 0\n                que.append((stop, b, 1))\n                # changes[1,0] = 0, changes[2,0] = 0, changes[7,0] = 0\n                # means for reach 1,2,7 we just 1 times of bus change\n                # (take the first bus also count as 1 change)\n                changes[stop, b] = 1\n\n        while que:\n            stop, bus, times = que.popleft()\n            # already reach the Target\n            if stop == T:\n                return times\n            for b in md[stop]:\n                if bus != b:\n                    for stop in routes[b]:\n                        # if I already reached this stop by bus, but I used few times for change\n                        if (stop, bus) in changes and changes[stop, bus] > 1 + times:\n                            que.append((stop, bus, 1 + times))\n                            # remember update the new times in cache\n                            changes[stop, bus] = 1 + times\n                        elif (stop, bus) not in changes:  # I never reached stop by this bus yet\n                            changes[stop, bus] = 1 + times\n                            que.append((stop, bus, 1 + times))\n                        # else: if I reached stop by bus, but I changed more times than the record in cache,\n                        # just prunning it\n                    # this sentences improve the performance greatly\n                    # the time is from 5000ms decrease to 260 ms\n                    routes[b] = []\n\n        return -1\n\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        routes = [set(stops) for stops in routes]\n        \n        #there is no reason to take the same bus twice\n        taken = set()\n        dq = collections.deque()\n        \n        neighbors = collections.defaultdict(list)\n        \n        for i in range(len(routes)):\n            if S in routes[i]:\n                dq.append(i)\n                taken.add(i)\n            for j in range(i):\n                if routes[i].intersection(routes[j]):\n                    neighbors[i].append(j)\n                    neighbors[j].append(i)\n        \n        count = 1\n        while dq:\n            size = len(dq)\n            for _ in range(size):\n                bus = dq.popleft()\n                if T in routes[bus]:\n                    return count\n                for nei in neighbors[bus]:\n                    if nei not in taken:\n                        dq.append(nei)\n                        taken.add(nei)\n            count += 1\n        \n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S==T:\n            return 0\n        \n        s2b = {}\n        for b, route in enumerate(routes):\n            for s in route:\n                if s not in s2b:\n                    s2b[s] = set()\n                s2b[s].add(b)\n                \n        q = collections.deque([S])\n        visited = set()\n        \n        buses = 1\n        while len(q):\n            l = len(q)\n            for _ in range(l):\n                curt = q.popleft()\n                # if curt in s2b:\n                for nb in s2b[curt]:\n                    if nb in visited:\n                        continue\n                    visited.add(nb)\n                    for ns in routes[nb]:\n                        if ns == T:\n                            return buses\n                        q.append(ns)\n            \n            buses += 1\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        queue = collections.deque()\n        graph = collections.defaultdict(set)\n        routes = list(map(set, routes))\n        seen, targets = set(), set()\n        for i in range(len(routes)):\n            if S in routes[i]:  # possible starting route number\n                seen.add(i)\n                queue.append((i, 1))  # enqueue\n            if T in routes[i]:  # possible ending route number\n                targets.add(i)\n            for j in range(i+1, len(routes)):\n                if routes[j] & routes[i]:  # set intersection to check if route_i and route_j are connected\n                    graph[i].add(j)\n                    graph[j].add(i)\n        while queue:\n            cur, count = queue.popleft()\n            if cur in targets:\n                return count\n            for nei in graph[cur]:\n                if nei not in seen:\n                    queue.append((nei, count+1))\n                    seen.add(nei)\n        return -1", "from collections import defaultdict\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        \n        br = []\n        start_r = []\n        for i, r in enumerate(routes):\n            br.append(set(r))\n            if S in r:\n                start_r.append(i)\n        \n        \n        if S == T:\n            return 0\n        \n        g = defaultdict(set)\n        for i in range(len(br)):\n            for j in range(i+1, len(br)):\n                if br[i].intersection(br[j]):\n                    g[i].add(j)\n                    g[j].add(i)\n        \n        \n        def bfs(r):\n            it = 1\n            q = [r]\n            vs = set()\n            \n            while q:\n                tmp = []\n                for ele in q:\n                    if ele in vs:\n                        continue\n                    vs.add(ele)\n                    if T in br[ele]:\n                        return it\n                    for n in g[ele]:\n                        tmp.append(n)\n                q = tmp\n                it += 1\n            \n            return math.inf\n        \n        res = math.inf\n        for r in start_r:\n            res = min(res, bfs(r))\n        \n        return res if res != math.inf else -1", "class Solution:\n    def numBusesToDestination(self, routes, S, T):\n        if S == T: return 0\n        queue = collections.deque()\n        graph = collections.defaultdict(set)\n        routes = list(map(set, routes))\n        seen, targets = set(), set()\n        for i in range(len(routes)):\n            if S in routes[i]:\n                seen.add(i)\n                queue.append((i, 1))  # enqueue\n            if T in routes[i]:\n                targets.add(i)\n            for j in range(i+1, len(routes)):\n                if routes[j] & routes[i]:\n                    graph[i].add(j)\n                    graph[j].add(i)\n        while queue:\n            cur, count = queue.popleft()\n            if cur in targets:\n                return count\n            for nei in graph[cur]:\n                if nei not in seen:\n                    queue.append((nei, count+1))\n                    seen.add(nei)\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        graph = collections.defaultdict(set)\n        \n        for i,route in enumerate(routes):\n            for r in route:\n                graph[r].add(i)\n                \n        queue = [[S,0]]\n        visited = set([S])\n        for stop,bus in queue:\n            if stop == T: return bus\n            for i in graph[stop]:\n                for j in routes[i]:\n                    if j not in visited:\n                        queue.append([j,bus+1])\n                        visited.add(j)\n                routes[i].clear()\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes, start, target):\n        if start == target: return 0\n\n        stop2Route = defaultdict(set)\n        route2Stop = defaultdict(set)\n        for i, stops in enumerate(routes):\n            for stop in stops:\n                route2Stop[i].add(stop)\n                stop2Route[stop].add(i)\n\n     #   return stop2Route, route2Stop\n        visited = set() \n        visitedStop = set()       \n        \n        q = [start]\n        step = 0\n        while q:\n            stack = []\n            step += 1\n            while q:\n                stop = q.pop()\n                for route in stop2Route[stop]:\n                    if route not in visited:\n                        if target in route2Stop[route]:\n                            if stop in route2Stop[route]:\n                                return step\n                        else:\n                            stack.append(route)\n                            visited.add(route)       \n                visitedStop.add(stop) \n                \n            for route in stack:\n                for stop in route2Stop[route]:\n                    if stop not in visitedStop:\n                        q.append(stop)\n         #   print(q, stop, stack, visited, step, visitedStop)\n         #   return\n\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T:\n            return 0\n        \n        graph = self.createGraph(routes)\n        \n        sourceBuses = self.getBuses(routes, S)\n        targetBuses = set(self.getBuses(routes, T))\n        \n        if not sourceBuses or not targetBuses:\n            return -1\n        \n        \n        \n        \n        queue = [sourceBuses]\n        visited = set(sourceBuses)\n        buses = 1\n        while queue:\n            curLevel = queue.pop()\n            newLevel = []\n            \n            for station in curLevel:\n                if station in targetBuses:\n                    return buses\n                \n                for conn in graph[station]:\n                    if conn not in visited:\n                    \n                        visited.add(conn)\n                        newLevel.append(conn)\n            \n            if newLevel:\n                queue.append(newLevel)\n                buses += 1\n        \n        return -1\n    \n    \n    def getBuses(self, routes, station):\n        buses = []\n        for i in range(len(routes)):\n            if station in set(routes[i]):\n                buses.append(i)\n        \n        return buses\n        \n    def createGraph(self, routes):\n        graph = defaultdict(set)\n        \n        for i,route in enumerate(routes):\n            routes[i] = set(route)\n        \n        for i in range(len(routes)):\n            for j in range(i+1, len(routes)):\n                if len(routes[i].intersection(routes[j])) > 0:\n                    graph[i].add(j)\n                    graph[j].add(i)\n        \n        return graph", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        # time complexity: O(m*n)\n        # space complexity: O(m*n)\n        stops = defaultdict(list) # stop: [buses]\n        for r, s in enumerate(routes):\n            for i in s: stops[i].append(r)\n        \n        q, buses, been = deque([S]), [0]*len(routes), set()\n        transfers = 0\n        while q:            \n            size = len(q)\n            for _ in range(size):\n                i = q.popleft()\n                if i == T: return transfers\n                for r in stops[i]:\n                    if buses[r]: continue\n                    buses[r] = 1\n                    for s in routes[r]:\n                        if s in been: continue\n                        been.add(s)\n                        q.append(s)      \n            transfers += 1          \n            \n        return -1\n                \n                    \n", "from queue import deque\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        # 1. create map of route_idx to List[route_idx]\n        # if two routes have same bus stops, attach edge to map.\n        # 2. go through routes, if any route has S, \n        # store idx of this route in s_lst; \n        # if any route has T, store idx this route in t_lst.\n        # 3. BFS queue of (route_idx, depth)\n        \n        # base cases\n        if S == T: \n            return 0\n        # 1\n        routes = list(map(set, routes))\n        r_map = {} # route_idx to List[route_idx]\n        for i, r1 in enumerate(routes):\n            for j in range(i+1, len(routes)):\n                if len(r1 & routes[j]) > 0:\n                    r_map.setdefault(i, []).append(j)\n                    r_map.setdefault(j, []).append(i)\n        # 2.\n        # NOTE: s_lst also functions as visitied lst.\n        s_lst, t_lst = [], []\n        for k, route in enumerate(routes):\n            if S in route:\n                s_lst.append(k)\n            if T in route:\n                t_lst.append(k)\n                \n        # base case\n        if T in s_lst:\n            return 1\n        # 3.\n        queue = deque([(idx, 1) for idx in s_lst])\n        while len(queue) > 0:\n            curr_route, level = queue.popleft()\n            if curr_route in t_lst:\n                return level\n            if curr_route not in r_map:\n                # dead end, no other routes overlap with curr\n                continue \n            for dest in r_map[curr_route]:\n                if dest not in s_lst:\n                    s_lst.append(dest)\n                    queue.append((dest, level + 1))\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        \n        # Builds graph.\n        graph = collections.defaultdict(list)  # Don't use set. See below.\n        for bus, stops in enumerate(routes):\n            bus = -bus - 1  # To avoid conflict with the stops.\n            \n            # `set.update` consumes extra memory, so a `list` is used instead.\n            graph[bus] = stops\n            for s in stops:\n                graph[s].append(bus)\n\n        # Does BFS.\n        dq = deque()\n        dq.append((S, 0))\n        seen = {S}\n        while dq:\n            node, depth = dq.popleft()\n            for adj in graph[node]:\n                if adj in seen: continue\n                if adj == T: return depth\n                # If `adj` < 0, it's a bus, so we add 1 to `depth`.\n                dq.append((adj, depth + 1 if adj < 0 else depth))\n                seen.add(adj)\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T:\n            return 0\n        \n        graph = self.createGraph(routes)\n        # print(g/raph)\n        \n        sourceBuses = self.getBuses(routes, S)\n        targetBuses = set(self.getBuses(routes, T))\n        \n        # print(sourceBuses, targetBuses)\n        if not sourceBuses or not targetBuses:\n            return -1\n        \n        \n        \n        \n        queue = [sourceBuses]\n        visited = set(sourceBuses)\n        buses = 1\n        while queue:\n            curLevel = queue.pop()\n            newLevel = []\n            \n            # print(curLevel)\n            for station in curLevel:\n                if station in targetBuses:\n                    return buses\n                \n                # print(graph[station], visited)\n                for conn in graph[station]:\n                    if conn not in visited:\n                    \n                        visited.add(conn)\n                        newLevel.append(conn)\n            \n            # print(newLevel)\n            if newLevel:\n                queue.append(newLevel)\n                buses += 1\n        \n        return -1\n    \n    \n    def getBuses(self, routes, station):\n        buses = []\n        for i in range(len(routes)):\n            if station in set(routes[i]):\n                buses.append(i)\n        \n        return buses\n        \n    def createGraph(self, routes):\n        graph = defaultdict(set)\n        \n        for i,route in enumerate(routes):\n            routes[i] = set(route)\n        \n        for i in range(len(routes)):\n            for j in range(i+1, len(routes)):\n                if len(routes[i].intersection(routes[j])) > 0:\n                    graph[i].add(j)\n                    graph[j].add(i)\n        \n        return graph", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        # BFS\n        # The first part loop on routes and record stop to routes mapping in to_route.\n        # The second part is general bfs. Take a stop from queue and find all connected route.\n        # The hashset seen record all visited stops and we won't check a stop for twice.\n        # We can also use a hashset to record all visited routes, or just clear a route after visit.\n        \n        to_routes = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                to_routes[j].add(i)\n        bfs = [(S, 0)]\n        seen = set([S])\n        for stop, bus in bfs:\n            if stop == T: return bus\n            for i in to_routes[stop]:\n                for j in routes[i]:\n                    if j not in seen:\n                        bfs.append((j, bus + 1))\n                        seen.add(j)\n                routes[i] = []  # seen route\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        if S == T:\n            return 0\n        \n        neighbors = collections.defaultdict(set)\n        \n        for j, route in enumerate(routes):\n            for i in route:\n                neighbors[i].add(j)\n                \n        stack = []\n        stack.append((S, 0))\n        visited = set()\n        visited.add(S)\n        visited_route = set()\n        \n        for stop, count in stack:\n            if stop == T:\n                return count\n\n            for neighbor in neighbors[stop]:\n                if neighbor not in visited_route:\n                    for bus in routes[neighbor]:\n                        if bus != stop and bus not in visited:\n                            stack.append((bus, count + 1))\n                            visited.add(bus)\n                        \n                #routes[neighbor] = []\n                visited_route.add(neighbor)\n                \n        return  -1\n            \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        # Get rid of duplicates if any in the lists inside 'routes'\n        routes = list(map(set, routes))\n        n = len(routes)\n        graph = defaultdict(set)\n        \n        for i in range(n):\n            for j in range(i+1,n):\n                if set(routes[i]).intersection(routes[j]):\n                    graph[i].add(j)\n                    graph[j].add(i)\n                    \n        \n        # Get source and destination\n        for i in range(n):\n            if S in routes[i]:\n                if T in routes[i]:\n                    return 1  \n                source = i\n            elif T in routes[i]:\n                dest = i\n                \n                \n                \n        q = deque([[source, 1]])\n        visited = [False]*n\n        visited[source] = True\n        \n        while q:\n            node, dis = q.popleft()\n            if node == dest:\n                return dis\n            for u in graph[node]:\n                if not visited[u]:\n                    visited[u] = True\n                    q.append([u, dis +1])\n                    \n        return -1\n            \n        \n", "\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        if len(routes) == 0:\n            return -1\n        \n        routesets = []\n        for route in routes:\n            routesets.append(set(route))\n            #print(routesets[-1])\n        \n        # This is all points where buses meet.\n        intersections = set()\n        for i in range(len(routesets) - 1):\n            set1 = routesets[i]\n            for j in range(i + 1, len(routesets)):\n                set2 = routesets[j]\n                intersections.update(set1.intersection(set2))\n        intersections.add(S)\n        intersections.add(T)\n        \n        #print(intersections)\n        \n        # This is all the routes at an intersection\n        i_to_routes = collections.defaultdict(list)\n        for i in intersections:\n            for ridx, route in enumerate(routesets):\n                if i in route:\n                    i_to_routes[i].append(ridx)\n        \n        for route in routesets:\n            route.intersection_update(intersections)\n        \n        #print(i_to_routes)\n       \n        heap = []\n        hist = set([S])\n        \n        heapq.heappush(heap, (0, 0, S))\n        \n        while heap:\n            n, _, loc = heapq.heappop(heap)\n            \n            if loc == T:\n                return n\n            \n            for route_idx in i_to_routes[loc]:\n                for edge in routesets[route_idx].difference(hist):\n                    hist.add(edge)\n                    heapq.heappush(heap, (n + 1, abs(edge - T), edge))\n        \n        return -1\n                \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        conn = collections.defaultdict(list)\n        for i, route in enumerate(routes):\n            for j in route:\n                conn[j].append(i)\n\n        bfs = collections.deque()\n        bfs.append((S, 0))\n        visited = set([S])\n        seen = set()\n        while bfs:\n            s, bus = bfs.popleft()\n            if s == T:\n                return bus\n            for i in conn[s]:\n                if i not in seen:\n                    for j in routes[i]:\n                        if j not in visited:\n                            visited.add(j)\n                            bfs.append((j, bus+1))\n                    # routes[i] = []\n                    seen.add(i)\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if not routes:\n            return None\n        if S == T:\n            return 0\n        stack = []\n        visited = set()\n        for i, bus in enumerate(routes):\n            if S in bus:\n                stack.append((bus, 1))\n                visited.add(i)\n                if T in bus:\n                    return 1\n        while stack:\n            bus, level = stack.pop(0)\n            bus = set(bus)\n            for i, b in enumerate(routes):\n                if i in visited:\n                    continue\n                if bus & set(b):\n                    stack.append((b, level +1))\n                    visited.add(i)\n                    if T in b:\n                        return level +1\n        return -1\n            \n", "from collections import defaultdict, deque\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], source_stop: int, target_stop: int) -> int:\n        if source_stop == target_stop: return 0\n        stops = defaultdict(set)\n        for i,route in enumerate(routes):\n            for stop in route:\n                stops[stop].add(i)\n        q = deque()\n        visited_stops = set()\n        visited_buses = set()\n        q.append((source_stop, 0))\n        while q:\n            stop_num, bus_num = q.popleft()\n            visited_stops.add(stop_num)\n            for other_bus in stops[stop_num]:\n                if other_bus in visited_buses: continue\n                visited_buses.add(other_bus)\n                for other_stop in routes[other_bus]:\n                    if other_stop == target_stop:\n                        return bus_num + 1\n                    if other_stop not in visited_stops:\n                        visited_stops.add(other_stop)\n                        q.append((other_stop, bus_num + 1))\n        return -1\n\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        stopbusmap = collections.defaultdict(set)\n        for bus, stops in enumerate(routes):\n            for stop in stops:\n                stopbusmap[stop].add(bus)\n        queue = []\n        for bus in stopbusmap[S]:\n            queue.append((routes[bus], [bus]))\n\n        length = 0\n        while queue:\n            length += 1\n            stops, taken = queue.pop(0)\n            for stop in stops:\n                if stop == T:\n                    return len(taken)\n                else:\n                    for nxt in stopbusmap[stop]:\n                        if nxt not in taken:\n                            queue.append((routes[nxt], taken+[nxt]))\n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        s2b = defaultdict(set)\n        for b in range(len(routes)):\n            routes[b] = set(routes[b])\n            for s in routes[b]:\n                s2b[s].add(b)\n        \n        visited = set()\n        q = [(1, b) for b in s2b[S]]\n        while q:\n            n, b = q.pop(0)\n            if b in visited:\n                continue\n            visited.add(b)\n            bs = set()\n            for s in routes[b]:\n                if s == T:\n                    return n\n                bs |= s2b[s]\n            for bn in bs:\n                q.append((n + 1, bn))\n            \n        return -1", "from collections import defaultdict\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        graph = defaultdict(list)\n        for idx, route in enumerate(routes):\n            for node in route:\n                graph[node].append(idx)\n        visited_stop = set([S])\n        visited_bus = [0 for _ in range(len(routes))]\n        queue = [(idx, 0) for idx in graph[S]] # bus idx\n        # for bus, _ in queue:\n        #     visited_bus[bus] = 1\n        while queue:\n            bus_id, depth = queue.pop(0)\n            new_stop = set(routes[bus_id]) - visited_stop\n            visited_stop = visited_stop | new_stop\n            for stop in new_stop:\n                if stop == T: return depth + 1\n                for bus in graph[stop]:\n                    if visited_bus[bus] == 0:\n                        visited_bus[bus] = 1\n                        queue.append((bus, depth + 1))\n        return -1", "class Solution:\n    def numBusesToDestination(self, bus_routes: List[List[int]], start: int, end: int) -> int:\n        # return self.approach_2(bus_routes, start, end)\n        if start == end:\n            return 0\n        on_stop = defaultdict(set)\n        for i, route in enumerate(bus_routes):\n            for stop in route:\n                on_stop[stop].add(i)\n        bfs = []\n        bfs.append((start, 0))\n        seen = set([start])\n        for stop, bus_count in bfs:\n            if stop == end:\n                return bus_count\n            for buses in on_stop[stop]:\n                for stops in bus_routes[buses]:\n                    if stops not in seen:\n                        if stops == end:\n                            return bus_count+1\n                        seen.add(stops)\n                        bfs.append((stops, bus_count+1))\n                bus_routes[buses] = []\n        return -1\n\n    def approach_2(self, bus_routes, start, end):\n        if start == end: return 0\n        graph = defaultdict(set)\n        bus_routes = list(map(set, bus_routes))\n        start_set = set()\n        end_set = set()\n        for bus, stops in enumerate(bus_routes):\n            for other_buses in range(bus+1, len(bus_routes)):\n                other_bus_route = bus_routes[other_buses]\n                if not other_bus_route.isdisjoint(stops):\n                    graph[bus].add(other_buses)\n                    graph[other_buses].add(bus)\n        for bus,route in enumerate(bus_routes):\n            if start in route: start_set.add(bus)\n            if end in route: end_set.add(bus)\n\n        queue = [(node, 1) for node in start_set]\n        for bus, changes in queue:\n            if bus in end_set: return changes\n            for nei in graph[bus]:\n                if nei not in start_set:\n                    start_set.add(nei)\n                    queue.append((nei, changes+1))\n        return -1\n    \n    def approach_3(self, buses, start, end):\n        on_stop = defaultdict(set)\n        for bus, stops in enumerate(buses):\n            for stop in stops:\n                on_stop[stop].add(bus)\n        bfs = [(start, 0)]\n        seen = set()\n        seen.add(start)\n        for stop, dist in bfs:\n            if stop == end:\n                return dist\n            for bus in on_stop[stop]:\n                for stops in buses[bus]:\n                    if end == start:\n                        return dist+1\n                    if stops not in seen:\n                        seen.add(stops)\n                        bfs.append((stops, dist+1))\n        return -1\n\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        \n        # traverse bus ROUTES instead of stops\n        if S==T: return 0\n        # build graph of routes\n        graph = defaultdict(set)\n        routes = list(map(set, routes))\n        seen = set()\n        target = set()\n        q = deque()\n        \n        for i in range(len(routes)):\n        #for i, r in enumerate(routes):\n            # build graph\n            for j in range(i+1, len(routes)):\n                if routes[i] & routes[j]:\n                    graph[i].add(j)\n                    graph[j].add(i)\n            # add starting routes\n            if S in routes[i]:\n                q.append((i, 1))    \n                seen.add(i)\n            # add ending routes\n            if T in routes[i]:\n                target.add(i)\n            \n        # traverse from start, return when reaching end\n        while q:\n            cur, count = q.popleft()\n            if cur in target:\n                return count\n            for rt in graph[cur]:\n                if rt not in seen:\n                    q.append((rt, count+1))\n                    seen.add(rt)\n        \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        num_buses = len(routes)\n        bus_to_stop = defaultdict(set)\n        for bus, stops in enumerate(routes):\n            bus_to_stop[bus] = set(stops)\n        \n        def update_buses_used():\n            for bus in range(num_buses):\n                if bus in buses_used:\n                    continue\n                if stops_reached & bus_to_stop[bus]:\n                    buses_used.add(bus)\n        \n        def update_stops_reached():\n            for bus in buses_used:\n                stops_reached.update(bus_to_stop[bus])\n        \n        buses_used = set()\n        stops_reached = {S}\n        pre_stop_count = 0\n        bus_count = 0\n        while len(stops_reached) > pre_stop_count:\n            if T in stops_reached:\n                return bus_count\n            pre_stop_count = len(stops_reached)\n            update_buses_used()\n            update_stops_reached()\n            bus_count += 1\n            \n        return -1\n\n    def numBusesToDestination(self, routes, S, T):\n        to_routes = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for j in route:\n                to_routes[j].add(i)\n        bfs = [(S, 0)]\n        seen = set([S])\n        for stop, bus in bfs:\n            if stop == T: return bus\n            for i in to_routes[stop]:\n                for j in routes[i]:\n                    if j not in seen:\n                        bfs.append((j, bus + 1))\n                        seen.add(j)\n                routes[i] = []  # seen route\n        return -1\n        \n        \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], s: int, t: int) -> int:\n        if s == t: return 0\n            \n        n_buses = len(routes)\n        \n        stops = defaultdict(lambda: set())\n        for i, route in enumerate(routes):\n            for stop in route:\n                stops[stop].add(i)\n                \n        g = [set() for _ in range(n_buses)]\n        for i, route in enumerate(routes):\n            for stop in route:\n                for bus in stops[stop]:\n                    if bus == i: continue\n                    g[i].add(bus)\n                \n        used = [False]*n_buses\n        q = collections.deque()\n        for bus in stops[s]:\n            q.append((bus, 1))\n            used[bus] = True\n        \n        while q:\n            bus, dist = q.popleft()\n            if bus in stops[t]:\n                return dist\n            for bus2 in g[bus]:\n                if not used[bus2]:\n                    q.append((bus2, dist+1))\n                    used[bus2] = True\n        return -1\n", "from collections import defaultdict\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        graph = defaultdict(list)\n        for idx, route in enumerate(routes):\n            for node in route:\n                graph[node].append(idx)\n        visited_node = set([S])\n        visited_route = [0 for _ in range(len(routes))]\n        queue = [(idx, 0) for idx in graph[S]] # route idx\n        for idx, _ in queue:\n            visited_route[idx] = 1\n        while queue:\n            id, depth = queue.pop(0)\n            new_nodes = set(routes[id]) - visited_node\n            visited_node = visited_node | new_nodes\n            for node in new_nodes:\n                if node == T: return depth + 1\n                for idx in graph[node]:\n                    if visited_route[idx] == 0:\n                        visited_route[idx] = 1\n                        queue.append((idx, depth + 1))\n        return -1 if S != T else 0", "class Solution:\n    def numBusesToDestination(self, routes, start, target):\n        if start == target: return 0\n        stop2Route = defaultdict(set)\n        route2Stop = defaultdict(set)\n        for i, stops in enumerate(routes):\n            for stop in stops:\n                route2Stop[i].add(stop)\n                stop2Route[stop].add(i)\n\n     #   return stop2Route, route2Stop\n        visited = set() \n        visitedStop = set()       \n        stack = []\n        q = [start]\n        step = 0\n        while q:\n            step += 1\n            while q:\n                stop = q.pop()\n                for route in stop2Route[stop]:\n                    if route not in visited:\n                        if target in route2Stop[route]:\n                            # in the same route\n                            if stop in route2Stop[route]:\n                                return step\n                        else:\n                            stack.append(route)\n                            \n                            visited.add(route)\n                            \n                visitedStop.add(stop) \n                \n            for route in stack:\n                for stop in route2Stop[route]:\n                    if stop not in visitedStop:\n                        q.append(stop)\n         #   print(q, stop, stack, visited, step, visitedStop)\n         #   return\n\n        return -1", "\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        if len(routes) == 0:\n            return -1\n        \n        routesets = []\n        for route in routes:\n            routesets.append(set(route))\n            #print(routesets[-1])\n        \n        # This is all points where buses meet.\n        intersections = set()\n        for i in range(len(routesets) - 1):\n            set1 = routesets[i]\n            for j in range(i + 1, len(routesets)):\n                set2 = routesets[j]\n                intersections.update(set1.intersection(set2))\n        intersections.add(S)\n        intersections.add(T)\n        \n        #print(intersections)\n        \n        # This is all the routes at an intersection\n        i_to_routes = collections.defaultdict(list)\n        for i in intersections:\n            for ridx, route in enumerate(routesets):\n                if i in route:\n                    i_to_routes[i].append(ridx)\n        \n        #print(i_to_routes)\n       \n        heap = []\n        hist = set([S])\n        \n        heapq.heappush(heap, (0, 0, S))\n        \n        while heap:\n            n, _, loc = heapq.heappop(heap)\n            \n            if loc == T:\n                return n\n            \n            for route_idx in i_to_routes[loc]:\n                for edge in routesets[route_idx].difference(hist):\n                    hist.add(edge)\n                    heapq.heappush(heap, (n + 1, abs(edge - T), edge))\n        \n        return -1\n                \n", "from collections import defaultdict\n\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        dist = {}\n        depth = 0\n        dist[S] = depth\n        vis_bs = set()\n        \n        # from cities to buses\n        c_to_bs = defaultdict(list)\n        for pos_b, b in enumerate(routes):\n            for c in b:\n                c_to_bs[c].append(pos_b)\n        \n        cur_cs = set([S])\n        \n        while len(cur_cs) > 0:\n            depth += 1\n            cur_bs = set()\n            for c in cur_cs: # new buses from last cities\n                for pos_b in c_to_bs[c]:\n                    if pos_b not in vis_bs:\n                        cur_bs.add(pos_b)\n                vis_bs |= cur_bs\n            cur_cs = set()\n            for pos_b in cur_bs:\n                for c in routes[pos_b]:\n                    if c not in dist:\n                        cur_cs.add(c)\n                        dist[c] = depth\n            if T in dist:\n                return dist[T]\n        \n        return -1", "from collections import defaultdict\nclass Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        new_routes = {}\n        for i, route in enumerate(routes):\n            new_routes[i] = set(route)\n        \n        start_buses = set()\n        target_buses = set()\n        queue = []\n        #connect buses which have common stops\n        stop_bus = defaultdict(set)\n        for bus, route in enumerate(routes):\n            for bus2 in range(bus+1, len(routes)):\n                if len(new_routes[bus].intersection(new_routes[bus2])) > 0:\n                    stop_bus[bus].add(bus2)\n                    stop_bus[bus2].add(bus)\n                    \n            if S in new_routes[bus]:\n                start_buses.add(bus)\n                queue.append((bus,1))\n            if T in new_routes[bus]:\n                target_buses.add(bus)\n \n        \n        \n        \n        while queue:\n            curr_bus, path = queue[0][0], queue[0][1]\n            queue = queue[1:]\n            if curr_bus in target_buses:\n                return path\n            for neigh in stop_bus[curr_bus]: \n                if neigh not in start_buses:\n                    start_buses.add(neigh)\n                    queue.append((neigh, path+1))\n        return -1\n        \n            \n        \n        \n        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if (S == T):\n            return 0\n        buses = collections.defaultdict(list)\n        for i, bus in enumerate(routes):\n            for stop in bus:\n                buses[stop].append(i)\n        # print(buses)\n        q = [S]\n        result = 0\n        took = set()\n        visited = set()\n        visited.add(S)\n        while (q):\n            for i in range(len(q), 0, -1):\n                now = q.pop(0)\n                for bus in buses[now]:\n                    if (bus not in took):\n                        for route in routes[bus]:\n                            if (route not in visited):                                \n                                if (route == T):\n                                    return result + 1\n                                q.append(route)\n                                visited.add(route)\n                        took.add(bus)\n            result += 1\n        \n        return -1\n                        \n                \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T: return 0\n        n = len(routes)\n        source = set()\n        target = set()\n        graph = [[] for _ in range(n)]\n\n        for i in range(n):\n            routes[i] = set(routes[i])\n            if S in routes[i]: source.add(i)\n            if T in routes[i]: target.add(i)\n\n        if not source or not target: return -1\n        if source & target:\n            return 1\n\n        for u in range(n):\n            for v in range(1, n):\n                if routes[u] & routes[v]:\n                    graph[u].append(v)\n                    graph[v].append(u)\n\n        queue = [(source.pop(), 1)]\n        seen = [0] * n\n        while queue:\n            new = []\n            for u, cost in queue:\n                if u in target:\n                    return cost\n                seen[u] = 1\n                for v in graph[u]:\n                    if seen[v]: continue\n                    seen[v] = 1\n                    new.append((v, cost + 1))\n            queue = new\n        return -1\n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        ans = 0\n        n = len(routes)\n        if S == T:\n            return 0\n        graph = collections.defaultdict(set)# stop -> bus #\n        queue = collections.deque()\n        visited_stop = set()\n        visited_bus = set()\n        for i in range(n):\n            for stop in routes[i]:\n                graph[stop].add(i)\n        print(graph)\n        queue.append(S)\n        visited_stop.add(S)\n        \n        while queue:\n            qLen = len(queue)\n            ans +=1\n            for i in range(qLen):\n                stop = queue.popleft()\n                for next_bus in graph[stop]:\n                    if next_bus in visited_bus:\n                        continue\n                    visited_bus.add(next_bus)\n                    for next_stop in routes[next_bus]:\n                        if next_stop in visited_stop:\n                            continue\n                        if next_stop == T:\n                            print('here')\n                            return ans\n                        queue.append(next_stop)\n                        visited_stop.add(next_stop)\n            # print(queue, visited_stop, visited_bus)\n            \n            # print(ans)\n        return -1 \n    \n# defaultdict(<class 'set'>, {1: {0}, 2: {0}, 7: {0, 1}, 3: {1}, 6: {1}})\n# deque([2]) {1, 2} {0}\n# deque([2, 7]) {1, 2, 7} {0}\n# 1\n# deque([3]) {1, 2, 3, 7} {0, 1}\n            \n\n           \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        \n        # if two routes share the same stop, they are reachable with each other\n        # mapping: stop -> routes\n        stops = collections.defaultdict(set)\n        # mapping: route -> reachable routes\n        reachable = collections.defaultdict(set)\n        for i, route in enumerate(routes):\n            for stop in route:\n                stops[stop].add(i)\n                for j in stops[stop]:\n                    reachable[i].add(j)\n                    reachable[j].add(i)\n                        \n        target_routes = stops[T]\n        queue = collections.deque(stops[S])\n        buses = 1\n        reached = stops[S]\n        while queue:\n            queue_len = len(queue)\n            for _ in range(queue_len):\n                route = queue.popleft()\n                if route in target_routes:\n                    #print(stops[S])\n                    #print(target_routes)\n                    #print(route)\n                    return buses\n                for other_route in reachable[route]:\n                    if other_route not in reached:\n                        reached.add(other_route)\n                        queue.append(other_route)\n            buses += 1\n        return -1\n                        \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if S == T:\n            return 0\n        stops = {}\n        for i in range(len(routes)):\n            for stop in routes[i]:\n                if stop not in stops:\n                    stops[stop] = [[i], False]\n                else:\n                    stops[stop][0].append(i)\n                    \n        next_stops = deque([S])\n        visited = [False for i in range(len(routes))]\n        remaining = 1\n        buses = 0\n        while len(next_stops) > 0:\n            cur = next_stops.popleft()\n            remaining -= 1\n            stops[cur][1] = True\n            for r in stops[cur][0]:\n                if not visited[r]:\n                    for s in routes[r]:\n                        if s == T:\n                            return buses + 1\n                        if not stops[s][1]:\n                            stops[s][1] = True\n                            next_stops.append(s)\n                    visited[r] = True\n            if remaining == 0:\n                remaining = len(next_stops)\n                buses += 1\n                \n        return -1", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if not routes:\n            return None\n        if S == T:\n            return 0\n        stack = []\n        visited = []\n        for i, bus in enumerate(routes):\n            if S in bus:\n                stack.append((bus, 1))\n                visited.append(i)\n                if T in bus:\n                    return 1\n        while stack:\n            bus, level = stack.pop(0)\n            bus = set(bus)\n            for i, b in enumerate(routes):\n                if i in visited:\n                    continue\n                if bus & set(b):\n                    stack.append((b, level +1))\n                    visited.append(i)\n                    if T in b:\n                        return level +1\n        return -1\n            \n", "class Solution:\n    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:\n        if not routes:\n            return None\n        if S == T:\n            return 0\n        stack = []\n        visited = []\n        for i, bus in enumerate(routes):\n            if S in bus:\n                stack.append((bus, 1))\n                visited.append(i)\n                if T in bus:\n                    return 1\n        while stack:\n            bus, level = stack.pop(0)\n            bus = set(bus)\n            for i, b in enumerate(routes):\n                if i in visited:\n                    continue\n                if len(bus & set(b)) > 0:\n                    stack.append((b, level +1))\n                    visited.append(i)\n                    if T in b:\n                        return level +1\n        return -1\n            \n"]