PROG-1133: รถไฟใต้ดิน (subway)

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;
const int M = 510;
const int INF = 2e9;
using pii = pair <int, int>;
int n, m;
vector <int> station[N], line[M], g[M];
vector < vector <int>> dis(M, vector <int> (M, INF));
vector < vector <bool>> visited(M, vector <bool> (M, false));
bool check[M][M];

int main(){

    scanf("%d%d", &n, &m);

    for(int i=1;i<=m;i++){
        int S;
        scanf("%d", &S);
        for(int j=1;j<=S;j++){
            int si;
            scanf("%d", &si);
            line[i].push_back(si);
            station[si].push_back(i);
        }
    }

    for(int u=1;u<=m;u++){ // line
        for(auto si: line[u]){ // station
            for(auto i: station[si]){ // line
                if(u == i or check[u][i] or check[i][u]) continue;
                check[u][i] = true;
                check[i][u] = true;
                g[i].push_back(u);
                g[u].push_back(i);
            }
        }
    }

    for(int i=1;i<=m;i++){
        int li = i;
        queue <pii> q;
        dis[li][li] = 0;
        q.push({0, li});
        while(!q.empty()){
            int u, d;
            u = q.front().second;
            d = q.front().first;
            q.pop();
            if(visited[li][u])
                continue;
            visited[li][u] = true;
            for(auto v: g[u]){
                if(!visited[li][v] and d + 1 < dis[li][v]){
                    dis[li][v] = d + 1;
                    q.push({d+1, v});
                }
            }
        }
    }

    int Q;
    scanf("%d", &Q);
    while(Q--){
        int a, b;
        scanf("%d%d", &a, &b);
        int ans = INF;
        for(auto sta: station[a]){
            for(auto stb: station[b]){
                ans = min(ans, dis[sta][stb]);
            }
        }
        if(ans >= INF) printf("impossible");
        else printf("%d", ans);
        printf("\n");
    }

    return 0;
}