Вот уже много лет существует мрачный культ 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" (без кавычек).