Складені світильники
Можливо, ви чули про популярну конструкторську іграшку, яку Францис отримала на свій день народження цього тижня. Ця іграшка складається з кількох металевих сфер, які можна з'єднати між собою за допомогою жорстких ланок (усі однакової довжини) з магнітами на кінцях. Кінці ланок прилипають до металевих сфер, і ланки можуть вільно обертатися та простягатися від сфери в будь-якому напрямку (утворюючи сферичний шарнір), що дозволяє створювати різноманітні цікаві конструкції. Францис зібрала кілька таких конструкцій і тепер хоче зберегти свої творіння, підвісивши їх у кутку своєї кімнати. Вона помітила, що для деяких конструкцій, коли вона піднімає їх і тримає за одну сферу, всі ланки складаються в одну тонку вертикальну лінію (див. малюнок) через притягування гравітацією і сферичні шарніри. Францис може підвісити свої творіння, прикріпивши одну сферу конструкції до стелі, і хоче заощадити місце, підвісивши кожну з них за сферу, яка призводить до найкоротшої складеної лінії. Вона вважає, що ті конструкції, які не висять як одна тонка лінія, займають занадто багато місця, і відкидає їх. Малюнок: Одна з конструкцій Францис (вгорі), та ж сама складена в пряму лінію довжиною 2 (внизу-зліва), і конструкція, яка не складеться в одну лінію, якщо підвісити її за будь-яку сферу (внизу-праворуч). Зверніть увагу, що на середньому діаграмі горизонтальні проміжки між сферами показані лише для ілюстрації! Математично, конструкція була б однією, нескінченно тонкою вертикальною лінією. Для простоти ми можемо вважати металеві сфери нескінченно малими точками, а ланки - відрізками одиничної довжини. Чи можете ви написати програму, щоб допомогти Францис визначити, скільки місця займуть її конструкції, і які з них відкинути? Ваше завдання - знайти найкоротшу можливу довжину складеної конструкції, якщо підвісити її за одну сферу, або повідомити, що немає способу підвісити конструкцію так, щоб вона склалася в нескінченно тонку пряму лінію.
Вхідні дані
Вхід міститиме кілька тестових випадків для аналізу. Кожен тестовий випадок описує повністю з'єднану конструкцію (тобто немає вільних, неприєднаних компонентів). Перша строка тестового випадку складається з двох цілих чисел, n та m, розділених пробілом, що вказують на кількість сфер (1 ≤ n ≤ 100) та ланок (0 ≤ m ≤ 1000), використаних у конструкції, відповідно. Сфери пронумеровані унікально від 1 до n. Наступні m рядків вхідних даних кожен містить два цілі числа, a_i та b_i (1 ≤ a_i, b_i ≤ n), що вказують на те, що Францис приєднала сферу a до сфери b у своїй конструкції. Зверніть увагу, що обидва кінці ланки не можуть бути приєднані до однієї сфери, і жодні дві ланки не приєднують одні й ті ж дві сфери. Порожній рядок розділяє вхідні тестові випадки, як показано в прикладі нижче. Один рядок, що містить "0 0" позначає кінець вводу; не обробляйте цей випадок.
Вихідні дані
Для кожного вхідного тестового випадку надрукуйте один рядок, що містить найкоротшу можливу довжину складеної конструкції. Якщо неможливо підвісити описану конструкцію за одну сферу так, щоб вона склалася в лінію, надрукуйте "неможливо".