Електронна пошта

Блог Аріадни сповнений смачними рецептами та корисними порадами щодо здорового і збалансованого способу життя. Не дивно, що він приваблює велику кількість читачів. Ця аудиторія тепер стабільна, і Аріадна вважає, що було б корисно, якби вони більше взаємодіяли і створили міцніше співтовариство, яке не обмежувалося б лише блогом.

Аріадна знає, що деякі з читачів вже є друзями або знайомими, і тому у них є адреси електронної пошти один одного. Вона вважає, що хорошим початком для розвитку спільноти було б, щоб у кожного був адрес електронної пошти кожного, щоб кожен міг зв'язатися з усією групою. Оскільки вона знає, що читачам її блогу також подобається робити речі "децентралізованим" способом, вона розробляє наступний протокол, який почне діяти з дня $d$:

• Кожного дня о $8$ ранку, кожен відправляє поточний список контактів зі своєї адресної книги всім своїм контактам з адресної книги.

• Кожного дня о $8$ вечора, кожен оновлює свою адресну книгу, додаючи всі нові отримані адреси електронної пошти.

Якщо у людини немає потреби вносити зміни о $8$ вечора, то процес вважається завершеним для цієї людини, і їй більше не потрібно відправляти електронні листи в наступні дні.

Ви досвідчений хакер і Вам вдалося отримати доступ до всіх адресних книг читачів блогу. Ви хочете здивувати і вразити Аріадну, повідомивши її про те, чи призведе запропонований нею процес до того, що кожен отримає адресу кожного іншого. Більш того, якщо успіх буде досягнутий, то Ви хочете оцінити скільки днів це займе. Більш точно, якщо процес увінчається успіхом, то Ви можете повідомити їй:

• кількість днів $e$ (включаючи перший) минулих до останнього оновлення, або

• кількість днів (включаючи перший) минулих до завершення процесу з усіх боків. Зверніть увагу, що згідно з визначенням Аріадни воно дорівнює $e+1$.

Вхідні дані

Перша рядок містить два цілих числа $n(2\le n\le 10^5)$ і $m(1\le m\le 10^5)$, відповідних кількості читачів і, кількості пар читачів, які спочатку мають адреси електронної пошти один одного. Читачі пронумеровані від $1$ до $n$.

Кожна з $m$ наступних рядків містить два цілих числа $i$ і $j$, що означають що читачі $i$ і $j$ спочатку мають адреси електронної пошти один одного. Зверніть увагу, що у читача $i$ є адреса читача $j$, і у читача $j$ є адреса читача $i$.

Вихідні дані

Виведіть одне ціле число, рівне:

• $-1$ якщо цей процес не призведе до того, що всі врешті-решт отримають адреси електронної пошти всіх інших, або

• розраховане необхідне кількість днів в іншому випадку. Зверніть увагу, що це число може бути рівним $0$.

Приклади

Ми припускаємо, що база читачів стабільна, тобто жоден читач не йде і жоден додатковий читач не приєднується протягом всього процесу.

Ми припускаємо, що кожен знає адресу своєї електронної пошти; отримання власної адреси просто ігнорується.

Вам не обов'язково бути "послідовними" у відповідях на кілька тестів. Це означає, що Ви можете вивести значення $e$ для одного тесту і $e+1$ для іншого.