Shortest path in unweighted path with BFS

shortest_unweighted.cpp

// https://cses.fi/problemset/result/5916157/
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<ll> bfs(vector<vector<ll>> &graph, ll n) {
    vector<ll> parent(n + 1);
    queue<ll> q;
    q.push(1);
    while (!q.empty()) {
        ll x = q.front();
        q.pop();
        for (ll i : graph[x]) {
            if (parent[i]) continue;
            parent[i] = x;
            q.push(i);
        }
    }
    if (!parent[n]) return {};
    vector<ll> ans = {n};
    while (ans.back() != 1) ans.push_back(parent[ans.back()]);
    reverse(ans.begin(), ans.end());
    return ans;
}

int main() {
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> graph(n + 1);
    while (m--) {
        ll a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<ll> ans = bfs(graph, n);
    if (ans.empty())
        cout << "IMPOSSIBLE";
    else {
        cout << ans.size() << '\n';
        for (ll i : ans) cout << i << ' ';
    }
}