Недавно Вася
узнал из Интернета о теории шести рукопожатий, согласно которой для любых двух
человек на Земле можно найти цепочку не более чем из семи попарно знакомых
людей. Более формально: для любых двух человек X1 и X7 на
Земле можно найти таких людей X2, X3, X4, X5
и X6, что X1 знаком с X2, X2 знаком
с X3 и так далее, в конце цепочки X6 знаком c X7.
Васю
заинтересовало, а чему же будет равно максимальное расстояние (то есть
количество рукопожатий), разделяющее участников его любимой группы в социальной
сети «Многошкольники». Помогите ему в решении данной
задачи.
Первая строка
входных данных содержит два целых числа N и M (2 ≤ N ≤ 2 000, 0 ≤
M ≤
20 000), где N – количество участников группы, M – количество пар знакомых
людей.
В следующих M
строках записаны по два числа ai и bi через пробел – номера участников,
которые знакомы друг с другом (1 ≤ ai
< bi ≤ N).
Выведите одно
число – ответ. Если найдутся такие участники, между которыми не существует ни
одной цепочки знакомств, то выведите -1.
|
Пример ввода 1
4 4
1 2
1 3
2 3
2 4
Пример вывода 1
2
|
Пример ввода 2
4 3
1 2
1 3
2 4
Пример вывода 2
3
|
Пример ввода 3
4 2
1 2
3 4
Пример вывода 3
-1
|
