Пчелиные ульи

Пчелы являются одними из самых трудолюбивых насекомых. Так как они собирают нектар и пыльцу с цветов, то должны ориентироваться по деревьям в лесу. Для простоты n деревьев пронумерованы числами от 0 до n - 1. Вместо того, чтобы бродить по лесу, они используют особый список путей. Путь соединяет два дерева, между которыми пчелы могут двигаться по прямой линии в любом направлении. Они не могут использовать пути, которых нет в их списке.

Поскольку технология была хорошо усовершенствована, пчелы также изменили свою рабочую стратегию. Вместо зависания над всеми деревьями в лесу, они нацеливались на конкретные деревья - преимущественно деревья с большим количеством цветов. Они планировали, что будут строить новые ульи в таких деревьях. После чего будут собирать еду только с этих деревьев. Пчелы также удалят некоторые пути со своего списка, чтобы исключить передвижения к деревьям, в которых отсутствуют ульи.

Теперь пчелы хотят построить ульи так, что если вдруг один из путей в их новом списке пропадет (некоторые птицы или животные побеспокоят их на этом пути), то будет еще возможно добраться от любого улья к другому, используя существующие пути.

Они не хотят выбрать меньше трех деревьев. Но поскольку строительство улей требует много работы, они хотят минимизировать их количество. Вам заданы деревья и пути, используемые пчелами. Вам следует построить новую колонию пчелиных улей для них.

Выходные данные

Для каждого теста вывести его номер и количество пчелиных улей, предложенных род колонию, либо 'impossible' если такую колонию образовать невозможно.

Замечание

Входные данные большие. Используйте быстрые методы чтения/записи.

3

3 3
0 1
1 2
2 0

2 1
0 1

5 6
0 1
1 2
1 3
2 3
0 4
3 4

Case 1: 3
Case 2: impossible
Case 3: 3