Message Route

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4signed main(){
5  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
6  int n,m; cin>>n>>m;
7  vector<int> adj[n];
8  for(int i=0,u,v;i<m;++i)
9    cin>>u>>v,
10    adj[--u].emplace_back(--v),
11    adj[v].emplace_back(u);
12  int di[n+1]; memset(di,0x3f,sizeof di);
13  di[0]=0;
14  queue<int> q; q.emplace(0);
15  while(q.size()){
16    int u=q.front(); q.pop();
17    for(auto&v:adj[u]) if(di[v]==di[n]){
18      q.emplace(v);
19      di[v]=di[u]+1;
20    }
21  }
22  if(di[n-1]==di[n]) cout<<"IMPOSSIBLE\n";
23  else{
24    vector<int> v; v.emplace_back(n-1);
25    for(int i=di[n-1]-1;i>=0;--i){
26      int nx;
27      for(auto&u:adj[v.back()])
28        if(di[u]==i) nx=u;
29      v.emplace_back(nx);
30    }
31    cout<<di[n-1]+1<<'\n';
32    for(int i=(int)v.size()-1;i>=0;--i) cout<<v[i]+1<<" "; cout<<'\n';
33  }
34  return 0;
35}