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();
        for (int u : adj[v]) {
            if (u == e){
                return true;
            }
            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);
	//adj2.resize(n);
	rep(i, 0, m){
	    int a, b;
	    cin >> a >> b;
	    adj[a-1].push_back(b-1);
	    //adj2[b-1].push_back(a-1);
	}
	
	if (!bfs(0,n-1)){
	    cout << "IMPOSSIBLE";
	    return 0;
	}
	
	topological_sort();
	
	vector<int> dist(n, -INF);
	dist[0] = 1;
	
	vector<vector<int>> sol(n);
	sol[0].push_back(1);
	
	for (int u : ans){
	    for (int v : adj[u]){
	        if (dist[v] < dist[u] + 1){
	            dist[v] = dist[u] + 1;
	            sol[v].insert(sol[v].end(), sol[u].begin(), sol[u].end());
	            sol[v].push_back(v+1);
	        }
	    }
	}
	//set<int> s(sol[n-1].begin(), sol[n-1].end());
 
	
// 	for (int u : ans){
// 	    cout << u << " ";
// 	}
// 	cout << endl;
	
// 	for (int u : dist){
// 	    cout << u << " ";
// 	}
	
// 	for (auto& u : sol){
// 	    for (int v : u){
// 	        cout << v << " ";
// 	    }
// 	    cout << endl;
// 	}
    cout << dist[n-1] << endl;
    for (int u: sol[n-1]){
        cout << u << " ";
    }

	return 0;
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: RUNTIME ERROR

Test 8

Verdict: RUNTIME ERROR

Test 9

Verdict: OUTPUT LIMIT EXCEEDED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: RUNTIME ERROR

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: RUNTIME ERROR

Test 16

Verdict: ACCEPTED

Test 17

Verdict: RUNTIME ERROR

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: RUNTIME ERROR

Test 21

Verdict: WRONG ANSWER