Longest route

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5;
vector<int> V[N];
int8_t Z[N];
vector<int> T;
pair<int,int> R[N];

void topo(int i) {
  if (Z[i] == 1) {
    assert(0);
  } else if (Z[i]) return;
  Z[i] = 1;
  for (int b : V[i]) topo(b);
  Z[i] = 2;
  T.push_back(i);
}

int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    V[a-1].push_back(b-1);
  }
  for (int i = 0; i < n; ++i) topo(i);
  reverse(T.begin(), T.end());
  for (int i : T) {
    if (i == 0) R[0] = {1,0};
    if (R[i].first == 0) continue;
    for (int j : V[i]) {
      if (R[i].first >= R[j].first) {
        R[j] = {R[i].first+1, i};
      }
    }
  }
  if (R[n-1].first == 0) {
    cout << "IMPOSSIBLE\n";
  } else {
    cout << R[n-1].first << '\n';
    vector<int> A;
    for (int j = 0, i = n-1; j < R[n-1].first; ++j) {
      A.push_back(i);
      i = R[i].second;
    }
    reverse(A.begin(),A.end());
    for (int i : A) {
      cout << i+1 << ' ';
    }
    cout << '\n';
  }
}

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