{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eВот уже много лет существует мрачный культ ICPC. По свидетельствам очевидцев, служители этого культа занимаются очень странными вещами. Они разбиваются на группы по \u003cstrong\u003e3\u003c/strong\u003e человека и поклоняются экрану, от которого исходит таинственное свечение, с силой бьют по каким-то кнопкам, сгруппированным на непонятного рода панели. Коммуникация эта, видимо, не является однонаправленной --- иногда “божество” подает какие-то знаки одобрения в ответ, и тогда раздаются дружные радостные крики служителей. У большинства нерадивых служителей, правда, ситуация эта происходит довольно редко. Чаще \"божество\" недовольно, что повергает поклоняющихся сначала в замешательство, а потом, нередко, и в уныние.\u003c/p\u003e\n\n\u003cp\u003eО природе \"божества\" ходят разные слухи. Некоторые утверждают, что \"божество\" существует во многих обличьях, каждое из которых управляется посвященным человеком (а может это и не человек вовсе, а существо более высокого порядка) --- Админом. Особенную известность получил так называемый Админ с Большой Бородой. А еще с давних пор ходит слух об особой благосклонности \"божества\" к кефиру... Впрочем, это уже какая-то нелепица, да и от темы задачи мы отвлеклись.\u003c/p\u003e\n\n\u003cp\u003eА вот собственно и сама задача. Собрались как-то раз \u003cstrong\u003eN \u003c/strong\u003eслужителей культа ICPC и решили, что традиционные методы поклонения устарели, надоели, да и вообще какие-то не особо зловещие. Постановили они, что вместо усиленного ожесточенного стука по клавиатуре следует им обмениваться темной энергией. Был разработан план --- множество из \u003cstrong\u003eM\u003c/strong\u003e пар (\u003cstrong\u003eA\u003c/strong\u003e, \u003cstrong\u003eB\u003c/strong\u003e), означающих, что служитель с номером \u003cstrong\u003eA\u003c/strong\u003e должен передавать энергию служителю с номером \u003cstrong\u003eB\u003c/strong\u003e (соответственно, служитель с номером \u003cstrong\u003eB\u003c/strong\u003e должен получать энергию от служителя с номером \u003cstrong\u003eA\u003c/strong\u003e).\u003c/p\u003e\n\n\u003cp\u003eНачали они действовать согласно плану, но энергия почему-то не передавалась. Как вы сами понимаете, проблема ну никак не может быть в том, что нет у служителей ICPC никакой темной энергии! Понимали это и сами служители. Спустя некоторое время осознали они, что для того, чтобы план сработал, следует им расположиться определенным образом. Начертили они магический круг и расположились по его границам.\u003c/p\u003e\n\n\u003cp\u003eКонечно, одного наличия круга недостаточно, требуется еще, чтобы процесс передачи энергии был ассоциирован с кругом. Общеизвестно, что передача энергии ассоциирована с кругом, если каждый служитель передает энергию непосредственно следующим за ним в круге (при обходе круга по часовой стрелке) служителям и получает энергию от непосредственно следующих перед ним в круге служителей.\u003c/p\u003e\n\n\u003cp\u003eОпределим то же самое более формально. Пусть \u003cstrong\u003enext(X)\u003c/strong\u003e --- номер служителя, стоящего непосредственно за служителем \u003cstrong\u003eX\u003c/strong\u003e по кругу (при обходе круга по часовой стрелке), а \u003cstrong\u003eprev(X)\u003c/strong\u003e --- номер служителя, стоящего непосредственно перед служителем \u003cstrong\u003eX\u003c/strong\u003e. Определим для \u003cstrong\u003ei\u003c/strong\u003e \u003e \u003cstrong\u003e1\u003c/strong\u003e величины \u003cstrong\u003enext^i(X) \u003d next(next^\\{i-1\\\u003c/strong\u003e(X))} и \u003cstrong\u003eprev^i(X) \u003d prev(prev^\\{i-1\\\u003c/strong\u003e(X))} (будем также считать, что \u003cstrong\u003enext^1(X) \u003d next(X)\u003c/strong\u003e и \u003cstrong\u003eprev^1(X) \u003d prev(X)\u003c/strong\u003e). Передача энергии ассоциирована с магическим кругом, если для каждого служителя выполнены следующие условия:\u003c/p\u003e\n\n\u003cul\u003e\n\u003cp\u003e\u003cli\u003e он передает энергию служителям \u003cstrong\u003enext^i(X)\u003c/strong\u003e, \u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003ei\u003c/strong\u003e ≤ \u003cstrong\u003eA\u003c/strong\u003e, где \u003cstrong\u003eA\u003c/strong\u003e --- общее количество служителей, которым он передает энергию;\u003c/p\u003e\n\n\u003cp\u003e\u003cli\u003e он получает энергию от служителей \u003cstrong\u003eprev^i(X)\u003c/strong\u003e, \u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003ei\u003c/strong\u003e ≤ \u003cstrong\u003eB\u003c/strong\u003e, где \u003cstrong\u003eB\u003c/strong\u003e --- общее количество служителей, от которых он получает энергию.\u003c/p\u003e\n\n\u003c/ul\u003e\n\n\u003cp\u003eНикогда еще цель не была так близка, однако расположиться по кругу таким образом, чтобы достичь ассоциированной передачи энергии, у собравшихся служителей ICPC не получилось. Как братья по культу ICPC, вы, конечно же, приложите все усилия, чтобы помочь им!\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eInput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eВходной файл содержит несколько тестов. В первой строке файла записано их количество \u003cstrong\u003eT\u003c/strong\u003e, далее следует описание \u003cstrong\u003eT\u003c/strong\u003e тестов.\u003c/p\u003e\n\n\u003cp\u003eОписание каждого теста начинается со строки, содержащей числа \u003cstrong\u003eN\u003c/strong\u003e и \u003cstrong\u003eM\u003c/strong\u003e. Далее следует \u003cstrong\u003eM\u003c/strong\u003e строк, описывающих план передачи энергии. Каждая из этих строк содержит два целых числа --- \u003cstrong\u003eA\u003c/strong\u003e и \u003cstrong\u003eB\u003c/strong\u003e. Служители пронумерованы числами от \u003cstrong\u003e1\u003c/strong\u003e до \u003cstrong\u003eN\u003c/strong\u003e.\u003c/p\u003e\n\n\u003cp\u003eВсе числа во входном файле целые. \u003cstrong\u003eN\u003c/strong\u003e ≥ \u003cstrong\u003e3\u003c/strong\u003e. Сумма значений \u003cstrong\u003eN\u003c/strong\u003e по всем тестам в одном файле не превосходит \u003cstrong\u003e100 000\u003c/strong\u003e. Сумма значений \u003cstrong\u003eM\u003c/strong\u003e по всем тестам в одном файле не превосходит \u003cstrong\u003e200 000\u003c/strong\u003e. \u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003eA\u003c/strong\u003e, \u003cstrong\u003eB\u003c/strong\u003e ≤ \u003cstrong\u003eN\u003c/strong\u003e. \u003cstrong\u003eA\u003c/strong\u003e ≠ \u003cstrong\u003eB\u003c/strong\u003e. В рамках одного теста каждая пара (\u003cstrong\u003eA\u003c/strong\u003e, \u003cstrong\u003eB\u003c/strong\u003e) присутствует не более одного раза. В рамках одного теста не могут одновременно присутствовать обе пары (\u003cstrong\u003eA\u003c/strong\u003e, \u003cstrong\u003eB\u003c/strong\u003e) и (\u003cstrong\u003eB\u003c/strong\u003e, \u003cstrong\u003eA\u003c/strong\u003e).\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eOutput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eДля каждого теста во входном файле выведите строку, содержащую перестановку чисел от \u003cstrong\u003e1\u003c/strong\u003e до \u003cstrong\u003eN\u003c/strong\u003e --- порядок, в котором следует стать служителям, чтобы достичь передачи энергии, ассоциированной с магическим кругом. Выведенный порядок должен соответствовать обходу круга по часовой стрелке. Если существует несколько решений, выведите любое из них. Если решения не существует, выведите \"\u003cstrong\u003eEpic fail\u003c/strong\u003e\" (без кавычек).\u003c/p\u003e\n\n"}},{"title":"Example","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n6 10\n1 6\n2 3\n2 4\n2 5\n3 1\n3 6\n4 3\n4 5\n5 3\n6 2\n3 0\n4 3\n1 2\n2 3\n3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6 2 4 5 3 1\n1 2 3\nEpic fail\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}