ltpq_cses_message_routes

#include<bits/stdc++.h>
using namespace std;
 
const int MAX = (int) 1e5 + 100;
vector<int> adj[MAX];
int dist[MAX], pre[MAX];
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int num_nodes, num_edges;
	cin >> num_nodes >> num_edges;
	
	for (int i = 1; i <= num_edges; i++) {
		int from,to;
		cin >> from >> to;
		adj[from].push_back(to);
		adj[to].push_back(from);
	}
	
	fill(pre, pre + 1 + num_nodes, 0); //line 43
	fill(dist, dist + 1 + num_nodes, -1);
	dist[1] = 1;
	
	queue<int> bfs; 
	bfs.push(1);
	while (bfs.size()) {
		int cur = bfs.front(); bfs.pop();
		for (int nxt : adj[cur]) if (dist[nxt] == -1) {
			dist[nxt] = dist[cur] + 1; 
			pre[nxt] = cur;
			bfs.push(nxt);
		}
	}
	
	if (dist[num_nodes] == -1) cout << "IMPOSSIBLE";
	else {
		cout << dist[num_nodes] << '\n';
		vector<int> path;
		int node = num_nodes;
		for (; node != 0; node = pre[node]) path.push_back(node);
		reverse(path.begin(), path.end());
		for (auto node : path) cout << node << ' ';
	}
}