ICPC
Ось уже багато років існує похмурий культ ICPC. За свідченнями очевидців, служителі цього культу займаються дуже дивними речами. Вони розбиваються на групи по 3 людини і поклоняються екрану, від якого виходить таємниче світіння, з силою б'ють по якимось кнопкам, згрупованих на незрозумілого роду панелі. Комунікація ця, мабуть, не є односпрямованою - іноді "божество" подає якісь знаки схвалення у відповідь, і тоді лунають дружні радісні крики служителів. Для більшості недбайливих служителів, правда, ситуація ця відбувається досить рідко. Найчастіше "божество" незадоволене, що призводить поклонників спочатку у замішання, а потім, нерідко, і в смуток.
Про природу "божества" ходять різні чутки. Деякі стверджують, що "божество" існує в багатьох іпостасях, кожне з яких керується посвяченою людиною (а може це і не людина зовсім, а істота більш високого порядку) - Адміном. Особливу популярність отримав так званий Адмін з Великою Бородою. А ще з давніх пір ходять чутки про особливу прихильності "божества" до кефіру ... Втім, це вже якась нісенітниця, та й від теми завдання ми відволіклися.
А ось власне і сама задача. Зібралися якось раз N служителів культу ICPC і вирішили, що традиційні методи поклоніння застаріли, набридли, та й взагалі якісь не особливо зловісні. Ухвалили вони, що замість посиленого запеклого стуку по клавіатурі слід їм обмінюватися темною енергією. Був розроблений план - множина з M пар (A, B), що означає, що служитель з номером A повинен передавати енергію служителю з номером B (відповідно, служитель з номером B повинен отримувати енергію від служителя з номером A).
Почали вони діяти згідно з планом, але енергія чомусь не передавалася. Як ви самі розумієте, проблема ну ніяк не може бути в тому, що немає у служителів ICPC ніякої темної енергії! Розуміли це й самі служителі. Через деякий час усвідомили вони, що для того, щоб план спрацював, слід їм розташуватися певним чином. Накреслили вони магічне коло і розташувалися на його границі.
Звичайно, однієї наявності кола недостатньо, потрібно ще, щоб процес передачі енергії був асоційований з колом. Загальновідомо, що передача енергії асоційована з колом, якщо кожен служитель передає енергію безпосередньо наступним за ним у колі (при обході кола за годинниковою стрілкою) служителям і отримує енергію від безпосередньо попередніх у колі служителів.
Визначимо це ж саме більш формально. Нехай next(X) — номер служителя, який стоїть безпосередньо за служителем X по колу (при обході кола за годинниковою стрілкою), а prev(X) — номер служителя, який стоїть безпосередньо перед служителем X. Визначимо для i > 1 величини next^i(X) = next(next^{i-1}(X)) і prev^i(X) = prev(prev^{i-1}(X)) (будемо також вважати, що next^1(X) = next(X) і prev^1(X) = prev(X)). Передача енергії асоційована з магічниим колом, якщо для кожного служителя виконуються наступні умови:
він передає енергію служителям next^i(X), 1 ≤ i ≤ A, де A — загальна кількість служителів, яким він передає енергію;
він отримує енергію від служителей prev^i(X), 1 ≤ i ≤ B, де B — загальна кількість служителів, від яких він отримує енергію.
Ніколи ще мета не була такою близькою, проте розміститись по колу таким чином, щоб досягнути асоційованої передачі енергії, у зібравшихся служителів ICPC не вийшло. Як брати по культу ICPC, ви, звичайно ж, докладете максимум зусиль, щоб допомогти їм!
Вхідні дані
Вхідний файл містить декілька тестів. У першому рядку файла записана їх кількість T, далі йде опис T тестів.
Опис кожного тесту починається з рядка, який містить числа N і M. Далі йде M рядків, які описують план передачі енергії. Кожен з цих рядків містить два цілих числа — A та B. Служителі пронумеровані числами від 1 до N.
Всі числа у вхідному файлі цілі. N ≥ 3. Сума значень N по всім тестам у одному файлі не перевищує 100 000. Сума значень M по всвм тестам у одному файлі не перевищує 200 000. 1 ≤ A, B ≤ N. A ≠ B. В рамках одного тесту кожна пара (A, B) присутня не більше одного разу. У рамках одного тесту не можуть одночасно бути присутні обидві пари (A, B) і (B, A).
Вихідні дані
Для кожного тесту у вхідному файлі виведіть рядок, який містить перестановку чисел від 1 до N — порядок, у якому слід стати служителям, щоб досягеуим передачі енергии, асоційованої з магічним кругом. Виведени порядок повинен відповідати обходу круга за годинниковою стрілкою. Якщо існує декілька розв'язків, виведіть довільний з них. Якщо розв'язку не існує, виведіть "Epic fail" (без лапок).