#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2,bmi")

using namespace std;
using namespace __gnu_pbds;

#define int long long
#define endl "\n"
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

constexpr int INF = 2e13;
constexpr int MOD = 1e9 + 7;
vector<vector<int>> gr;


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, g;
    cin >> n >> m >> g;
    gr.assign(n, {});
    bool ok = false;
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        v--;
        u--;
        if (v == n - 1 && u == 0) ok = true;
        gr[u].push_back(v);
    }
    vector<vector<int>> way(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        way[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            for (int u : gr[j]) {
                way[i][j] += way[i][u];
            }
        }
    }
    vector<int> dp(n);
    for (int i = 0; i < n; i++) {
        if (i) {
            dp[i] = dp[i - 1];
        }
        for (int u : gr[i]) {
            dp[i] = max(dp[i], dp[u] + way[u][i]);
        }
    }
    cout << dp[n - 1];
}
