EduBrick
← вернуться к уроку · Обходы: в глубину и в ширину

Диаметр дерева

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

Дано дерево — связный граф без циклов, в котором ровно n1n - 1 ребро.

Диаметр дерева — наибольшее расстояние между двумя его вершинами. Найдите его.

Формат ввода

В первой строке числа nn от 11 до 21052 \cdot 10^5 и mm, равное n1n - 1. Во второй строке 2m2m чисел: пары концов рёбер. Граф гарантированно является деревом.

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

Одно число.

Примеры

ввод
1 0
вывод
0

Примечание

Запустите обход из любой вершины и найдите самую далёкую — она обязательно окажется концом какого-то диаметра. Запустите обход уже из неё: наибольшее расстояние и будет ответом. Двух обходов достаточно.

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