Задачи
ICPC
ICPC
Вот уже много лет существует мрачный культ ICPC. По свидетельствам очевидцев, служители этого культа занимаются очень странными вещами. Они разбиваются на группы по \textbf{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