printРабочее место участника

printЗадачи

2165. Хвост графа

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

28893.png

Хвостом графа назовем последовательность связанных вершин, такую что первая связана только со второй, вторая только с первой и третьей, а последующие только с соседними. Последняя вершина может быть связана либо только с предпоследней, либо с предпоследней и вершиной, которая не входит в наш хвост.
Теперь у Пети новое хобби – находить у графа самый длинный хвост, где длина хвоста определяется как количество вершин входящих в него. Но пока Петя не всегда может узнавать длину хвоста. Помогите ему.
В первой строке входного файла заданы числа `n` (`1\ ≤\ n\ ≤\ 100000`) – количество вершин в графе и `m` (`1\ ≤\ m\ ≤\ 200000`) – количество ребер в графе. Следующие `m` строк содержат по два числа `a_i,\ b_i` – номера вершин, которые соединяет соответствующее ребро.
Каждая пара вершин соединена не более чем одним ребром, никакое ребро не соединяет вершину с ней же. Из любой вершины существует путь до любой другой вершины графа.
В выходной файл требуется вывести одно целое число – длину самого длинного хвоста графа.

Пример ввода

9 11
1 2
1 3
1 4
2 3
2 4
3 4
4 5
4 6
4 7
7 8
8 9

Пример вывода

3
Источник: neerc.ifmo.ru/school
loading