Longest route

#include<bits/stdc++.h>
using namespace std;
 
using Edges = vector<vector<int>>; 
 
int INF = 0x3f3f3f3f;

struct TopoSort {
    enum class Status : uint8_t { to_visit, visiting, visited };
 
    const Edges& graph;
    const int n;
    vector<Status> status;
    vector<int> order;
    vector<int>::reverse_iterator it;
 
    TopoSort(const Edges& graph) :
        graph(graph),
        n(graph.size()),
        status(n, Status::to_visit),
        order(n),
        it(order.rbegin()) {}
 
    bool Sort() 
    {
        for (int i = 0; i < n; ++i) 
            if (status[i] == Status::to_visit && !Dfs(i)) 
                return false;
        return true;
    }
 
    bool Dfs(const int u) 
    {
        status[u] = Status::visiting;
        for (const int v : graph[u]) 
        {
            if (status[v] == Status::visiting) 
                return false;
            if (status[v] == Status::to_visit && !Dfs(v)) 
                return false;
        }
        status[u] = Status::visited;
        *it++ = u;
        return true;
    }
};
 
int main()
{
    int n, m;
    cin >> n >> m;
    Edges edge(n+1);
    for(int i=1; i<=m; i++)
    {
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
    }
    TopoSort T(edge);
    T.Sort();

    // Calc the f
    vector<int> dis(n+1), father(n+1);
    for(int i=1; i<=n; i++)
        dis[i] = -INF;
    dis[1] = 1;
    
    for(int i=1; i<=n; i++)
    {
        int x = T.order[i-1];
// cout << x << " ";
        if(dis[x] == -INF)
            continue;
        for(auto y: edge[x])
        {
            if(dis[y] < dis[x] + 1)
            {
                father[y] = x;
                dis[y] = dis[x] + 1;
            }
        }
    }

    if(dis[n] <= 0)
    {
        cout << "IMPOSSIBLE";
        return 0;
    }
    int max_dis = dis[n], now_city = n;

    vector<int> list;
    while (father[now_city])
    {
        list.push_back(now_city);
        now_city = father[now_city];
    }
    list.push_back(now_city);
    
    reverse(list.begin(), list.end());

    cout << max_dis << endl;
    for(auto x: list)
        cout << x << " ";
    
    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