Shared code

//PPAP_1264589
#include <bits/stdc++.h>
#define Task "A"
#define up(i,a,b) for (int i = a; i <= b; i++)
#define down(i,a,b) for (int i = a; i >= b; i--)
#define pii pair<int, int>
#define f first
#define s second
#define ep emplace_back
#define bit(x,i) ((x >> i) & 1)
using namespace std;
const int LIM = 1010580540;
const int MOD = 1e9 + 7;
 
const int maxn = 1e5 + 10;
int dp[maxn];
int check[maxn];
int tr[maxn];
vector<pii> a[maxn];
int n,m;
 
void in(){
    cin >> n >> m;
    up(i,1,m){
        int u,v;
        cin >> u >> v;
        if (check[u] == v) continue;
        check[u] = v;
        a[u].ep(v, -1);
    }
}
 
priority_queue<pii, vector<pii>, greater<pii>> P;
void Dijkstra(){
    memset(dp, 60, sizeof(dp));
    dp[1] = -1;
    P.push({dp[1], 1});
    while (!P.empty()){
        pii x = P.top();
        P.pop();
        int u = x.s;
        int curw = x.f;
        if (curw > dp[u]) continue;
        for (pii T : a[u]){
            int v = T.f;
            int w = T.s;
            if (dp[v] > curw + w){
                dp[v] = curw + w;
                tr[v] = u;
                P.push({dp[v], v});
            }
        }
    }
}
 
void Fpath(){
    int x = n;
    vector<int> path;
    while (x != 1){
        path.ep(x);
        x = tr[x];
    }
    path.ep(1);
    reverse(path.begin(), path.end());
    for (auto x : path) cout << x << " ";
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(Task".inp", "r")){
        freopen (Task".inp", "r", stdin);
        freopen (Task".out", "w", stdout);
    }
 
    in();
    Dijkstra();
 
    if (dp[n] == LIM) cout << "IMPOSSIBLE";
    else {
        cout << -dp[n] << "\n";
        Fpath();
    }
}
 
// Algorithmic logic