Longest route

#include <bits/stdc++.h>
 
#define all(x) x.begin(), x.end()
 
using namespace std;
using ll = long long;
 
const int MAXN = 1e5 + 1;
vector<int> g[MAXN];
const int INF = (int)1e9;
int nxt[MAXN];
 
int dfs(int u, int n, vector<int>& ans) {
    if (ans[u] != INF) {
        return ans[u];
    }
    
    ans[u] = -INF;
    if (u == n - 1)
        ans[u] = 1;
    for (auto v : g[u]) {
        int newRes = dfs(v, n, ans) + 1;
        if (newRes > ans[u]) {
            ans[u] = newRes;
            nxt[u] = v;
        }       
    }
    return ans[u];
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n = 0, m = 0;
	cin >> n >> m;
 
	int a = 0, b = 0;
	for (int i = 0; i < m; ++i)
	{
		cin >> a >> b;
		g[a - 1].push_back(b - 1);
	}
 
	vector<int> maxPath(n, INF);
        int ans = dfs(0, n, maxPath); 
 
	if (ans >= 0)
	{
		cout << ans << "\n";
		int u = 0;
		while (u != n - 1)
		{
			cout << u + 1 << " ";
			u = nxt[u];
		}
		cout << n << "\n";
	}
	else
	{
		cout << "IMPOSSIBLE\n";
	}
 
 
	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