Задача №112781. Хвост графа
Петя с детства любит воздушных змеев и камни. Ему очень нравится наблюдать, как они летают. Особенно Пете нравится смотреть, как развевается хвост змея. На одном из уроков математики, которую Петя тоже любит, учитель рассказывал про графы. Во время рассказа, в качестве примера, учитель на доске нарисовал граф, похожий на воздушного змея. Пете сразу обратил внимание на хвост графа.
Хвостом графа назовем последовательность связанных вершин, такую что первая связана только со второй, вторая только с первой и третьей, а последующие только с соседними. Последняя вершина может быть связана либо только с предпоследней, либо с предпоследней и вершиной, которая не входит в наш хвост.
Теперь у Пети новое хобби — находить у графа самый длинный хвост, где длина хвоста определяется как количество вершин входящих в него. Но пока Петя не всегда может узнавать длину хвоста. Помогите ему.
В первой строке входного файла заданы числа n (3 ≤ n ≤ 100000) — количество вершин в графе и m (1 ≤ m ≤ 200000) — количество ребер в графе. Следующие m строк содержат по два числа ai, bi — номера вершин, которые соединяет соответствующее ребро.
Каждая пара вершин соединена не более чем одним ребром, никакое ребро не соединяет вершину с ней же. Из любой вершины существует путь до любой другой вершины графа.
В выходной файл требуется вывести одно целое число — длину самого длинного хвоста графа.
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
n ≤ 100 и m ≤ 1000. Решение оценивается в 40 баллов.
Дополнительные ограничения отсутствуют. Решение оценивается в 60 баллов.