Сім королівств
Джон Дейн - правитель величезної країни, яка називається Сім Королівств. У нього є дві сестри Арія та Санса, і він хоче подарувати їм деякі міста з Семи Королівств. Він буде правити містами, що залишились, а якщо таких не залишиться, то направиться до стіни - колосального укріпленню вздовж північного кордону Семи Королівств, де і стане головнокомандуючим. Арія - леді Вінтерфелли, а Санса - леді Королівської Землі. Міста у Семи Королівствах (включаючи Вінтерфелл та Королівську Землю) з'єднані один з одним мережею доріг (хоча деякі міста можуть бути недоступними з інших міст, так як вони розміщені або на островах, або знаходяться у стані війни з цими містами). Прямої дороги між Вінтерфелл та Королівськю Землею немає, і у них навіть немає спільного сусіднього міста.
Джон хоче виділити кожній зі своїх сестер набір міст таким чином, щоб кожне місто з набору було зв'язано прямою дорогою з усіма іншими містами цього ж набору, а усі інші міста, які не входять у жоден з цих двох наборів, були б також зв'язані один з одним прямою дорогою. Набір міст Арії повинен включатм Вінтерфелл, а набір міст Санси повинен включати Королівську Землю. Джону необхідна Ваша допомога, щоб визначити, чи це можливо. І якщо відповідь стверджувальна, то Вам потрібно вказати міста для кожного набору.
Вхідні дані
Вхідні дані складаються з одного тесту. Перший рядок містить кількість міст n (1 ≤ n ≤ 2000) та кількість доріг m. Кожен з наступних m рядків містить два цілих числа x_i та y_i (1 ≤ x_i, y_i ≤ n) - різні номери міст, з'єднаних дорогою. Вінтерфелл - місто номер 1, Королівська Земля - місто номер 2 у мережі доріг.
Вихідні дані
Якщо розбити міста на множини як вимагається в умові задачі неможливо, то вивести слово impossible. Інакше вивести два рядки: у першому міста, віддані Арії, а у другому міста, віддані Сансі. Якщо існує декілька розв'язків, то виведіть довільний.