CCCPaste

9c91d3bc828c0

#include<bits/stdc++.h>
#define MAXN 100010

using namespace std;

vector<int> grafo[MAXN];

queue<int> q;
int marc[MAXN], dist[MAXN], pai[MAXN];
int n;

void bfs(int s){
q.push(s);
marc[s] = 1;
dist[s] = 0;
pai[s] = -1;
while(!q.empty()){
int v = q.front();
q.pop();
for(int viz : grafo[v]){
if(marc[viz] == 0){
marc[viz] = 1;
q.push(viz);
dist[viz] = dist[v]+1;
pai[viz] = v;
}
}
}
}

int main(){
int m; scanf("%d %d", &n, &m);

for(int i = 1; i <= m; i++){
int a, b; scanf("%d %d", &a, &b);
grafo[a].push_back(b);
grafo[b].push_back(a);
}
bfs(1);

if(dist[n] == 0){
printf("IMPOSSIBLE\n");
return 0;
}
printf("%d\n", dist[n]+1);

//Encontra o menor caminho da fonte até o vértice v
vector<int> path;
path.push_back(n);
while(pai[n] != -1){
n = pai[n];
path.push_back(n);
}
//path.push_back(n);

reverse(path.begin(),path.end());

for(auto v : path){
printf("%d ", v);
}
}