Сталкер

#include <iostream>
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ef emplace_back
#define x first
#define y second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ld, ld> pld;
typedef pair<ll, ll> pl;
typedef vector<int> veci;
typedef vector<bool> vecb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;

const int INF_I = 1e9;
const ll INF_LL = 1e18;
const int MOD = 1000000007;
const double eps = 1e-6;
//(clock() * 1.0 / CLOCKS_PER_SEC)
void solve(){

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<vector<vector<short>>> g(k+1, vector<vector<short>>(n + 1));
    vector<set<short>> c(n + 1);
    for (int i = 1; i <= k; i++){
        int m;
        cin >> m;
        while (m--){
            int a, b;
            cin >> a >> b;
            a--, b--;
            c[a].emplace(i);
            c[b].emplace(i);
            g[i][a].eb(b);
            g[i][b].eb(a);
        }
    }

    vvb u(k+1, vecb(n+1));
    list<pair<short, short>> deq;
    vector<vector<short>> d(k+1, vector<short>(n+1, 1 << 13));
    d[0][0] = 0;
    deq.eb(mp(0, 0));
    while (!deq.empty()){
        pi cur = deq.front();
        deq.pop_front();
        if (u[cur.x][cur.y])
            continue;
        u[cur.x][cur.y] = true;
        if (cur.y == n-1 && cur.x != 0){
            cout << d[cur.x][cur.y] << "\n";
            return 0;
        }
        if (cur.x == 0){
            for (int i : c[cur.y]) {
                if (!u[i][cur.y]) {
                    if (d[i][cur.y] > d[cur.x][cur.y] + 1)
                        d[i][cur.y] = d[cur.x][cur.y] + 1;
                    deq.eb(mp(i, cur.y));
                }
            }
        }
        else{
            if (!u[0][cur.y]) {
                d[0][cur.y] = min(d[0][cur.y], d[cur.x][cur.y]);
                deq.ef(mp(0, cur.y));
            }
            for (int i : g[cur.x][cur.y]){
                if (u[cur.x][i])
                    continue;
                d[cur.x][i] = min(d[cur.x][i], d[cur.x][cur.y]);
                deq.ef(mp(cur.x, i));
            }
        }
    }
    cout << "-1" << endl;

    return 0;
}