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