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

Вхідні дані

Перший рядок містить два цілих числа 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$.

Приклади

Пояснення до прикладу $1$. Процес відбувається наступним чином:

У день $d$ о $8$ ранку:

• Читач $1$ надсилає адресу читача $2$ читачу $2$.

• Читач $2$ надсилає адреси читачів $1$ та $3$ читачам $1$ та $3$.

• Читач $3$ надсилає адреси читачів $2$ та $4$ читачам $2$ та $4$.

• Читач $4$ надсилає адресу читача $3$ читачу $3$.

У день $d$ після оновлення о $8$ вечора:

• Адресна книга читача $1$ була оновлена і містить адреси читачів $2$ та $3$.

• Адресна книга читача $2$ була оновлена і містить адреси читачів $1,3$ та $4$.

• Адресна книга читача $3$ була оновлена і містить адреси читачів $1,2$ та $4$.

• Адресна книга читача $4$ була оновлена і містить адреси читачів $2$ та $3$.

У день d + 1 о $8$ ранку:

• Читач $1$ надсилає адреси читачів $2$ та $3$ читачам $2$ та $3$.

• Читач $2$ надсилає адреси читачів $1,3$ та $4$ читачам $1,3$ та $4$.

• Читач $3$ надсилає адреси читачів $1,2$ та $4$ читачам $1,2$ та $4$.

• Читач $4$ надсилає адреси читачів $2$ та $3$ читачам $2$ та $3$.

У день d + 1 після оновлення о $8$ вечора:

• Адресна книга читача $1$ була оновлена і містить адреси читачів $2,3$ та $4$.

• Процес завершився для читача $2$, оскільки оновлення не було.

• Процес завершився для читача $3$, оскільки оновлення не було.

• Адресна книга читача $4$ була оновлена і містить адреси читачів $1,2$ та $3$.

У день d + 2 о $8$ ранку:

• Читач $1$ надсилає адреси читачів $2,3$ та $4$ читачам $2,3$ та $4$.

• Читач $4$ надсилає адреси читачів $1,2$ та $3$ читачам $1,2$ та $3$.

У день d + 2 після оновлення о $8$ вечора:

• Процес завершився для читача $1$, оскільки оновлення не було.

• Процес завершився для читача $4$, оскільки оновлення не було.

Останнє оновлення відбувається в день d + 1, через $2$ дні, що минули. Процес завершився для всіх у день d + 2, через $3$ дні, що минули. Вивід прикладу містить перше значення $2$. Виведення другого значення $3$ є також правильною альтернативою.

Примітка

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

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

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