CSES - Shared codeLink to this code: https://cses.fi/paste/971f0de8610c3b856640b3/
#include<bits/stdc++.h>
using namespace std;
class MessageRoute{
private:
int n;
vector<vector<int>>graph;
vector<int> prevNode;
public:
MessageRoute(int n,vector<vector<int>>&graph){
this->n=n;
this->graph=graph;
prevNode.resize(n+1,0);
}
vector<int> MinComputers(){
queue<int>que;
que.push(1);
int node;
prevNode[1]=-1;
while(!que.empty()){
node=que.front();
que.pop();
for(int connectedCompuer:graph[node]){
if(prevNode[connectedCompuer]==0){
prevNode[connectedCompuer]=node;
que.push(connectedCompuer);
}
}
}
if(prevNode[n]==0){
return {};
}
vector<int> computers;
node=n;
while(node!=-1){
computers.push_back(node);
node=prevNode[node];
}
reverse(computers.begin(),computers.end());
return computers;
}
};
int main(){
int n,m,a,b;
cin>>n>>m;
vector<vector<int>>graph(n+1);
for(int i=0;i<m;i++){
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
MessageRoute route(n,graph);
vector<int> computers=route.MinComputers();
if(computers.size()==0){
cout<<"IMPOSSIBLE"<<endl;
}else{
cout<<computers.size()<<endl;
for(auto i:computers){
cout<<i<<" ";
}
}
return 0;
}