static constexpr int pow(int x, int p) {
    int res = 1;
    int base = x;

    while (p) {
        if (p & 1) res *= base;
        base *= base;
        p /= 2;
    }

    return res;
}


class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        stop_id_to_rout_id_ = vector<vector<int>>(Solution::kMaxStopId);
        auto graph = BuildGraph(routes);
        return SearchTargetStop(graph, S, T);
    }

private:
    static constexpr int kMaxStopId{ pow(10, 6) };
    static constexpr int kMaxRouts{ 500 };

    vector<vector<int>> stop_id_to_rout_id_;

    vector<vector<int>> BuildGraph(const vector<vector<int>>& routes) {

        for (int rout_id = 0; rout_id < routes.size(); ++rout_id) {
            for (auto stop_id : routes[rout_id])
                stop_id_to_rout_id_[stop_id].push_back(rout_id);
        }

        vector<vector<int>> graph(kMaxRouts);

        for (auto& rout_ids : stop_id_to_rout_id_) {
            for (int i = 1; i < rout_ids.size(); ++i) {
                for (int j = 0; j < i; ++j) {
                    graph[rout_ids[i]].push_back(rout_ids[j]);
                    graph[rout_ids[j]].push_back(rout_ids[i]);
                }
            }
        }

        return graph;
    }

    int SearchTargetStop(const vector<vector<int>>& graph, int S, int T) {
        queue<pair<int, int>> to_process;
        vector<int> visited(Solution::kMaxRouts);

        for (auto route_id : stop_id_to_rout_id_[S]) { // add all routs containing start stop
            if (find(stop_id_to_rout_id_[T].begin(), stop_id_to_rout_id_[T].end(), route_id) !=
                    stop_id_to_rout_id_[T].end())
                return (S == T) ? 0 : 1;
            to_process.push({ route_id, 1 });
        }

        while (!to_process.empty()) {
            auto[curr_rout_id, dist] = to_process.front();
            to_process.pop();
            visited[curr_rout_id] = true;

            for (auto adj_rout_id : graph[curr_rout_id]) {
                if (visited[adj_rout_id]) continue;
                if (find(stop_id_to_rout_id_[T].begin(), stop_id_to_rout_id_[T].end(), adj_rout_id) !=
                        stop_id_to_rout_id_[T].end())
                    return dist + 1;

                to_process.push({ adj_rout_id, dist + 1 });
            }
        }

        return -1;
    }
};