Ступінь поділу

У нашому дедалі більш взаємопов'язаному світі передбачалося, що кожен на Землі пов'язаний з усіма іншими не більше ніж на шість ступенів поділу. У цій задачі Ви повинні знайти максимальний ступінь поділу для заданої мережі людей. Для будь-яких двох людей ступінь поділу - це мінімальна кількість стосунків, які необхідно подолати, щоб з'єднати двох людей. Для мережі максимальний ступінь поділу - це найбільший ступінь поділу між будь-якими двома людьми в мережі. Якщо в мережі є пара людей, які не пов'язані ланцюжком стосунків, мережа відключається. Як показано нижче, мережа описується набором симетричних відносин, кожне з яких пов'язує двох людей. Кожен зв'язок являє собою відносини між двома людьми.

Вхідні дані

Складається з декількох тестів, що описують мережі людей. Для кожного набору даних перший рядок містить два цілих числа: $p$ $(2\le p\le 50)$ - кількість людей у мережі та $r$ $(r\ge 1)$ - кількість зв'язків у мережі. Після цього першого рядка йдуть $r$ відносин. Кожен зв'язок складається з двох рядків, які являють собою імена пов'язаних людей у мережі. Імена унікальні та не містять пробілів. Оскільки людина може бути пов'язана більш ніж з однією іншою людиною, ім'я може зустрічатися в наборі даних кілька разів. За останнім тестом йде рядок, що містить два нулі.

Вихідні дані

Для кожної мережі виведіть її номер, за яким слідує максимальний ступінь поділу. Якщо мережа відключена, виведіть DISCONNECTED. Після відповіді для кожної мережі виведіть порожній рядок. Використовуйте формат, показаний у прикладі вихідних даних.

Приклади

Примітка

У першому тесті мережа має максимальний ступінь поділу $2$. У другому тесті мережу вимкнено.