PROG-T1133: Subway

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;
const int M = 500;

vector<int> line[N + 1];
int dist[M + 1][M + 1];

int main(){

    int nStation, nLine;
    scanf("%d%d", &nStation, &nLine);

    // APSP Setup
    for(int u = 1; u <= nLine; ++u){
        for(int v = 1; v <= nLine; ++v){
            if(u == v){
                dist[u][v] = 0;
            } else {
                dist[u][v] = 1e9;
            }
        }
    }
    for(int u = 1; u <= nLine; ++u){
        int nPass;
        scanf("%d", &nPass);
        for(int j = 1; j <= nPass; ++j){
            int station;
            scanf("%d", &station);
            for(int v : line[station]){
                if(u == v){
                    continue;
                }
                dist[u][v] = 1;
                dist[v][u] = 1;
            }
            line[station].push_back(u);
        }
    }

    // Floyd-Warshall Algorithm
    for(int k = 1; k <= nLine; ++k){
        for(int u = 1; u <= nLine; ++u){
            for(int v = 1; v <= nLine; ++v){
                dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v]);
            }
        }
    }

    int Q;
    scanf("%d", &Q);
    while(Q--){
        int st, ed;
        scanf("%d%d", &st, &ed);
        int mn = 1e9;
        for(int u : line[st]){
            for(int v : line[ed]){
                mn = min(mn, dist[u][v]);
            }
        }
        if(mn == 1e9){
            cout << "impossible\n";
        } else {
            cout << mn << '\n';
        }
    }

    return 0;
}