This is a very simple and detailed solution for the CSES problem Longest Flight Route which a problem involving graph theory. The problem statement aims to find the longest route between 2 cities (1 and n) such that the route covers maximum no of distinct cities in the route. If we cannot reach the nth node from the 1st node, "IMPOSSIBLE" has to be printed. Else, print the length of route along with the cities encountered.

The solution of this problem can be intuitively thought to be to find the maximum route using the depth first traversal in a graph. 1. The input is taken as an adjacency list represented the edges in a directed graph. 2. A visited array and mark_dfs() function is used to check whether nth node is reachable or not. If it is not reachable, "IMPOSSIBLE" is printed. 3. The core logic of the solution lies in storing the maximum distance of a node from the nth node in the dp array. A dfs is implemented from the 1st node traversing to all the child nodes. The nth node returns a len of 1 which is the base case of recursion. Whenever a len greater than the already stored len is encountered, the max_len is updated and stored in the dp array as supposed to a basic dynamic programming approach. 4. The child array stores the child_node which gave the max_len route which is used to print the path of flight and used in forward traversal. 5. The printing of route involves forward traversal in the child array, where the node is reallocated to the child[node] in each pass until we reach the nth node. 6. The time complexity of the above approach is O(n+m) for the mark_dfs() function. The time complexity of dfs() is O(n) as the dp approach reduces the dfs to a linear time complexity. Hence the overall time complexity can be around O(2n+m) or O(n) for simplified purposes. 7. The space complexity of given approach is O(3n) wherein three arrays namely, vis,child and dp are used for functional purposes.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD1 998244353
#define INF 1e18
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define fori(i,a,b) for(int i=a; i<b;i++)
#define Y { cout <<"YES"<< endl;}
#define NN { cout <<"NO"<< endl;}

const int mod = 1e9+7;


//function to check whether nth node is reachable
void mark_dfs(ll node, vector<ll> &vis, vector<ll> adj[]){
    vis[node] = 1;
    for(auto child : adj[node]){
        if(!vis[child]){
            mark_dfs(child,vis,adj);
        }
    }
}

//function to return the max_len and store the path using child array
ll dfs(ll node, vector<ll> &dp, vector<ll> adj[],int n, vector<ll> &child){
    //base condition
    if(node==n) return dp[n] = 1;
    //memoization step
    if(dp[node]!=-1) return dp[node];
    ll len = 0;
    //standard dfs approach
    for(auto v : adj[node]){
        ll tmp = dfs(v,dp,adj,n,child);
        //temp_len checks whether the len is coming from the nth node or not
        ll temp_len = tmp==0?0:1+tmp;
        if(temp_len>len){
            // updating the child node and len
            child[node] = v;
            len = temp_len;
        }
    }
    //dp assignment step
    return dp[node] = len;
}
 
int main(){
    ll n,m;
    cin>>n>>m; 
    vector<ll> adj[n+1];
    fori(i,0,m){
        ll x,y;
        cin>>x>>y;
        adj[x].pb(y);
    }

    vector<ll> vis(n+1,0);
    //function call to check if nth node is reachable
    mark_dfs(1,vis,adj);
    if(!vis[n]) cout<<"IMPOSSIBLE\n";
    else{
        vector<ll> dp(n+1,-1);
        vector<ll> child(n+1,0);
        ll len = dfs(1,dp,adj,n,child);
        int node = 1;
        vector<ll> path;
        //forward traversal to print the path.
        while(node){
            path.pb(node);
            node = child[node];
        }
        cout<<len<<endl;
        for(auto it : path){
            cout<<it<<" ";
        }
    }
    return 0;

}