Code : Strongly Connected 2

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

void solve() {
    int n, m;

    cin >> n >> m;

    vector<mint> dp(n);
    // dp[i] denotes the number of graphs where index of the max vertex
    // reachable from 0 is i.

    dp[0] = 1;

    vector<pair<int, int>> edges;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        edges.push_back({u, v});
    }

    sort(edges.begin(), edges.end());
    for (auto [x, y] : edges) {
        // We ignore this edge, then the configuration will not change.
        // Hence, we copy dp to ndp instead of setting ndp to 0s.
        auto ndp = dp;

        // Now we deal with the case where the edge will definitely be taken.
        for (int i = 0; i < n; i++) {
            // The configuration will not change if it is :
            // 1. A backward edge.
            // 2. An edge ending at or before i.
            // 3. An edge starting starting strictly after i.
            if (x > y || y <= i || x > i) {
                ndp[i] += dp[i];
            } else {
                // If we include this edge, max reach will incease
                ndp[y] += dp[i];
            }
        }
        swap(dp, ndp);
    }

    cout << dp[n - 1].val() << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
}