CSES – Message Route

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 1e5+5;
int n,m,from[maxn];
vector<int> G[maxn];
int vis[maxn];
//
void bfs(int start){
    queue<int> q;
    memset(vis,-1,sizeof(vis));
    q.push(start);
    vis[start] = 0;
    while(!q.empty()){
        int cur = q.front(); q.pop();
        if(cur == n) return;
        for(int adj : G[cur]){
            if(vis[adj] != -1) continue;
            vis[adj] = vis[cur] + 1;
            from[adj] = cur;
            q.push(adj);
        }
    }
}
signed main(){
    fastio;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b; cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    bfs(1);
    if(vis[n] == -1) cout<<"IMPOSSIBLE\n";
    else{
        int now = n;
        vector<int> ans;
        while(now != 1){
            ans.push_back(now);
            now = from[now];
        }
        ans.push_back(1);
        cout<<ans.size()<<"\n";
        reverse(ans.begin(),ans.end());
        for(int i:ans) cout<<i<<" ";
        cout<<"\n";
    }
    return 0;
}