Недавно Вася узнал из Интернета о теории шести рукопожатий, согласно которой для любых двух человек на Земле можно найти цепочку не более чем из семи попарно знакомых людей. Более формально: для любых двух человек X₁ и X₇ на Земле можно найти таких людей X₂, X₃, X₄, X₅ и X₆, что X₁ знаком с X₂, X₂ знаком с X₃  и так далее, в конце цепочки X₆ знаком c X₇.

Васю заинтересовало, а чему же будет равно максимальное расстояние (то есть количество рукопожатий), разделяющее участников его любимой группы в социальной сети «Многошкольники». Помогите ему в решении данной задачи.

Первая строка входных данных содержит два целых числа N и M (2 ≤ N ≤ 2 000, 0 ≤ M ≤ 20 000), где N – количество участников группы, M – количество пар знакомых людей.

В следующих M строках записаны по два числа a_i и b_i через пробел  –  номера участников, которые знакомы друг с другом (1 ≤ a_i < b_i ≤ 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