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