CourseScheduleVlad

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


#define NMAX (int)(1000)
#define INF (int)(1e9)
#define ll long long
#define mkp make_pair
#define mkt make_tuple
#define lsb(x) (x & -x)

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V, typename W>
void __print(const std::tuple<T, V, W> &x) {cerr << '{'; __print(std::get<0>(x)); cerr << ','; __print(std::get<1>(x)); cerr << ','; __print(std::get<2>(x)); cerr << '}';}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif


int T, N, M;
int k;
int x, y;
int in[NMAX];

vector<int> G[NMAX];
vector<int> parent[NMAX];
vector<int> doneInQuarter;
vector<int> dp;
bitset<NMAX> viz;


void maxPath(int nod) { // O(N+M) DP; dp[x] = length of longest path starting at `x`

    viz[nod] = true;
    for (const int& neigh: G[nod]) {
        if (!viz[neigh])
            maxPath(neigh);
        dp[nod] = max(dp[nod], dp[neigh] + 1);
    }
    return ;
}


int main() {

//    freopen("instances/large19.in", "r", stdin);
//    freopen("instances/large19.res", "w", stdout);



    cin >> N >> M;
    dp = vector<int>(N + 1);
    doneInQuarter = vector<int>(N + 1);

    for (int i = 0; i < M; ++i) {
        cin >> x >> y;
        in[y] ++;
        G[x].push_back(y);
        parent[y].push_back(x);
    }
    cin >> k;


    for (int x = 1; x <= N; ++x)
        if (!viz[x])
            maxPath(x);



    priority_queue<pair<int, int>> pq; // {maxPath, node}
    for (int x = 1; x <= N; ++x)
        if (in[x] == 0)
            pq.push({dp[x], x});



    int quarters = 0;

    while (!pq.empty()) {

        queue<pair<int, int>> Q;
        quarters ++;
        int sz = pq.size();

        for (int it = 0; it < min(sz, k); ++it) {

            const auto [maxPath, x] = pq.top();
            pq.pop();

            doneInQuarter[x] = quarters;

            for (const int &y: G[x]) {

                in[y]--;
                if (in[y] == 0) {
                    Q.push({dp[y], y});
                }
            }
        }
        while (!Q.empty()) {
            pq.push(Q.front());
            Q.pop();
        }

    }

    cout << quarters;
    return 0;
}