MessageRoute.cpp

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

const int N = 1e5 + 2;
vector<bool>visited(N,false);
vector<int> adj [N];
vector<long long> dist(N);
vector<int>parent(N);


void BFS(int n){
    dist[n] = 0;

    queue<int>q;
    q.push(n);

    while(!q.empty()){
        int current = q.front();
        q.pop();

        for(int next : adj[current]){
            if(dist[next] == LONG_LONG_MAX){
                dist[next] = dist[current] + 1;
                q.push(next);
                parent[next] = current;
            }
        }
    }
}

int main(){
    int n,m;
    cin >> n >> m;

    for(int i = 0 ; i < m ; i ++){
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }


    for(int i = 1 ; i <= n ; i ++){
        dist[i] = LONG_LONG_MAX;
    }

    BFS(1);

    if(dist[n] == LONG_LONG_MAX)cout << "IMPOSSIBLE";
    else{
        cout << dist[n] + 1 << endl ;
        
        int ans[dist[n]+1];

        ans[dist[n]] = n;
        int i = parent[n];
        int z = dist[n] - 1;
        while(i != 1){
            ans[z--] = i;
            i = parent[i];
        }
        ans[0] = 1;
        for(int i = 0 ; i <= dist[n] ; i ++)cout << ans[i] << " ";
    }

    return 0;
}