EduBrick

Самая длинная цепочка компонент

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

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

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

Формат ввода

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

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

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

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

Примеры

ввод
3 3
1 2
2 3
3 1
вывод
3
ввод
5 5
1 2
2 1
2 3
3 4
4 3
вывод
4
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.