Longest Flight Route

    1#include <bits/stdc++.h>
    2using namespace std;
    3 
    4int main(){
    5    ios::sync_with_stdio(0); cin.tie(0);
    6    int n, m; cin >> n >> m;
    7    vector<vector<int>> adj(n);
    8    vector<int> indegree(n);
    9    for(int i = 0; i < m; i++){
    10        int a, b; cin >> a >> b; a--; b--;
    11        adj[a].push_back(b);
    12        indegree[b]++;
    13    }
    14    queue<int> q;
    15    for(int i = 0; i < indegree.size(); i++){
    16        if(indegree[i] == 0) q.push(i);
    17    }
    18    vector<int> result;
    19    while(!q.empty()){
    20        int node = q.front(); q.pop();
    21        result.push_back(node);
    22        for(int nxt : adj[node]){
    23            indegree[nxt]--;
    24            if(indegree[nxt] == 0) q.push(nxt);
    25        }
    26    }
    27    vector<int> dist(n, -1e9);
    28    dist[0] = 1;
    29    vector<int> parent(n, -1);
    30    for(int u : result){
    31        if(dist[u] == -1e9) continue;
    32        for(int v : adj[u]){
    33            if(dist[u] + 1 > dist[v]){
    34                parent[v] = u;
    35                dist[v] = dist[u] + 1;
    36            }
    37        }
    38    }
    39    if(dist[n - 1] == -1e9){
    40        cout << "IMPOSSIBLE" << '\n';
    41    } else {
    42        cout << dist[n - 1] << '\n';
    43        vector<int> path;
    44        for(int i = n - 1; i != -1; i = parent[i]) path.push_back(i);
    45        for(int i = path.size() - 1; i >= 0; i--) cout << path[i] + 1 << (i == 0 ? "\n" : " ");
    46    }
    47}