Бджолині вулики
Пчоли — одні з найпрацьовитіших комах. Збираючи нектар і пилок з квітів, вони повинні орієнтуватися серед дерев у лісі. Для зручності n дерев пронумеровані від 0 до n - 1. Замість того, щоб блукати по лісі, вони користуються спеціальним списком шляхів. Шлях з'єднує два дерева, між якими бджоли можуть рухатися по прямій в будь-якому напрямку. Вони не можуть використовувати шляхи, яких немає в їхньому списку.
Завдяки вдосконаленій технології, бджоли змінили свою робочу стратегію. Замість того, щоб відвідувати всі дерева в лісі, вони зосереджуються на певних деревах — переважно тих, що мають багато квітів. Вони планують будувати нові вулики на цих деревах і збирати їжу лише з них. Бджоли також видалять деякі шляхи зі свого списку, щоб уникнути пересування до дерев без вуликів.
Тепер бджоли хочуть розмістити вулики так, щоб у разі зникнення одного з шляхів у їхньому новому списку (через птахів або тварин, які можуть їх потурбувати), все ще можна було дістатися від одного вулика до іншого, використовуючи наявні шляхи.
Вони не хочуть вибирати менше трьох дерев. Але оскільки будівництво вулика вимагає багато зусиль, вони прагнуть мінімізувати їх кількість. Вам надано дерева і шляхи, які використовують бджоли. Вам слід спроектувати нову колонію бджолиних вуликів для них.
Вхідні дані
Починається з кількості тестів t (t ≤ 50).Кожен тест починається з порожнього рядка. Наступний рядок містить два цілі числа n (2 ≤ n ≤ 500) і m (0 ≤ m ≤ 20000), де n — кількість дерев, а m — кількість шляхів. Кожен з наступних m рядків містить два числа u v (0 ≤ u, v < n, u ≠ v), що визначають шлях між деревами u і v. Між деревами u і v може існувати не більше одного шляху, кожен шлях у вхідних даних задається лише один раз.
Вихідні дані
Для кожного тесту вивести його номер і кількість бджолиних вуликів, запропонованих для колонії, або 'impossible', якщо таку колонію утворити неможливо.
Примітка
Вхідні дані великі. Використовуйте швидкі методи читання/запису.
