E. Длиннейший путь

В ориентированном ациклическом графе найдите наибольшее количество рёбер в пути. Путь может начинаться и заканчиваться где угодно.

В обычном графе это невозможно, в ациклическом - линейно

Поиск длиннейшего простого пути в произвольном графе - NP-трудная задача: из неё следует гамильтонов путь. Но в ациклическом графе слова «простой» не нужно: повторить вершину всё равно нельзя, раз нет циклов. И задача становится обычной динамикой.

а обрабатывать вершины надо в топологическом порядке - тогда к моменту обработки $v$ все $\text{dp}[u]$ готовы. Ответ - максимум по всем вершинам.

Обойтись одним проходом

Отдельный топологический порядок строить не обязательно: динамику удобно считать прямо внутри алгоритма Кана, проталкивая значение вперёд по ребру:

while (!queue.empty()) {
    int v = queue.front(); queue.pop();
    best = std::max(best, dp[v]);
    for (int to : g[v]) {
        dp[to] = std::max(dp[to], dp[v] + 1);
        if (--deg[to] == 0) queue.push(to);
    }
}

Зачем это нужно

Длиннейший путь в ациклическом графе - это «сколько шагов займёт самая длинная цепочка зависимостей». В расписании работ это критический путь, в сборке - глубина зависимостей, в задаче про минимакс из этого же занятия - проверка, хватит ли ходов.

Подробнее: «Динамика на ациклическом графе».

В первой строке - числа $n$ и $m$ ($1 \le n \le 10^5$, $0 \le m \le 2 \cdot 10^5$).

В следующих $m$ строках - рёбра $u$, $v$ ациклического графа. Возможны кратные рёбра.

Выведите наибольшее число рёбер в пути.