EduBrick

I. Длиннейшая цепочка компонент

3000 мс · 256 МБ · всё или ничего

Постройте конденсацию и найдите в ней наибольшее число компонент на одном пути.

Конденсация ациклична, а в ациклическом графе длиннейший путь считается динамикой по топологическому порядку: f[c]=1+max⁡f[преемник]f[c] = 1 + \max f[\text{преемник}], где максимум берётся по рёбрам конденсации, а для стоков он равен нулю.

Отдельно сортировать конденсацию не нужно: алгоритм Косарайю нумерует компоненты в топологическом порядке, поэтому достаточно пройти по номерам от последнего к первому.

Это первая на занятии задача, где ациклическость конденсации используется по-настоящему: в исходном графе с циклами никакого длиннейшего пути не существует.

Формат ввода

Первая строка содержит числа nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5) и mm (0≤m≤2⋅1050 \le m \le 2 \cdot 10^5).

Далее идут mm строк с рёбрами. Возможны кратные рёбра и петли.

Формат вывода

Одно число — наибольшее количество компонент на пути.

Примеры

ввод
4 4
2 1
3 2
2 3
4 3
вывод
3
ввод
3 3
1 2
2 3
3 1
вывод
1
Войдите, чтобы отправлять решения.