Longest route

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define int long long
const int INF = 1e18;
typedef pair<int, int> pii;
typedef vector<int> vi;

int n;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> ans;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
    ans.push_back(v);
}

void topological_sort() {
    visited.assign(n, false);
    ans.clear();
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    reverse(ans.begin(), ans.end());
}

bool bfs(int s, int e) {
    queue<int> q;
    vector<bool> used(n);

    q.push(s);
    used[s] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        if (v == e){
            return true;
        }
        for (int u : adj[v]) {
            if (!used[u]) {
                used[u] = true;
                q.push(u);
            }
        }
    }
    return false;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    
    int m;
    cin >> n >> m;
    adj.resize(n);
    rep(i, 0, m){
        int a, b;
        cin >> a >> b;
        adj[a-1].push_back(b-1);
    }
    
    if (!bfs(0, n-1)) {
        cout << "IMPOSSIBLE";
        return 0;
    }
    
    topological_sort();
    
    vector<int> dist(n, -INF);
    vector<int> parent(n, -1);
    dist[0] = 1;

    for (int u : ans) {
        for (int v : adj[u]) {
            if (dist[v] < dist[u] + 1) {
                dist[v] = dist[u] + 1;
                parent[v] = u;
            }
        }
    }
    
    cout << dist[n-1] << endl;

    vector<int> path;
    for (int v = n-1; v != -1; v = parent[v]) {
        path.push_back(v + 1); 
    }
    reverse(all(path));

    for (int v : path) {
        cout << v << " ";
    }

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED