ICPC
For many years, there has been a mysterious cult surrounding the ICPC. Eyewitnesses report that its followers engage in peculiar rituals. They form groups of three and worship a screen that emits an enigmatic glow, fervently pressing buttons on a strange panel. This interaction is not entirely one-sided; occasionally, the "deity" responds with signs of approval, prompting cheers from the followers. However, for most, this approval is rare. More often, the "deity" is displeased, leaving the followers confused and often disheartened.
Rumors abound regarding the nature of this "deity." Some suggest it exists in multiple forms, each overseen by an Admin, who may not even be human but a higher being. The Admin with the Great Beard is particularly famous. There are even whispers about the deity's fondness for kefir, but that's straying into nonsense, and we must focus on the task at hand.
Here is the task. Once, N followers of the ICPC cult gathered and decided that their traditional worship methods were outdated, dull, and not sufficiently sinister. They resolved to exchange dark energy instead of frantically typing on keyboards. They devised a plan involving M pairs (A, B), indicating that follower A should transfer energy to follower B (and thus, follower B should receive energy from follower A).
They attempted to execute this plan, but the energy failed to transfer. Clearly, the issue wasn't a lack of dark energy among the ICPC followers! They soon realized that for the plan to succeed, they needed to arrange themselves in a specific way. They drew a magic circle and positioned themselves along its perimeter.
Of course, merely having a circle isn't enough; the energy transfer must also be linked to the circle. It is known that energy transfer is associated with a circle if each follower transfers energy directly to the next follower in the circle (when moving clockwise) and receives energy from the follower immediately preceding them in the circle.
Let's define this more formally. Let next(X) be the follower standing directly after follower X in the circle (when moving clockwise), and prev(X) be the follower standing directly before follower X. For i > 1, define next^i(X) = next(next^{i-1}(X)) and prev^i(X) = prev(prev^{i-1}(X)) (we also assume next^1(X) = next(X) and prev^1(X) = prev(X)). Energy transfer is associated with the magic circle if for each follower the following conditions are met:
They transfer energy to followers next^i(X), 1 ≤ i ≤ A, where A is the total number of followers to whom they transfer energy;
They receive energy from followers prev^i(X), 1 ≤ i ≤ B, where B is the total number of followers from whom they receive energy.
Despite being so close to their goal, the ICPC followers couldn't arrange themselves around the circle to achieve the desired energy transfer. As fellow members of the ICPC cult, you are called upon to assist them!
Input
The input file contains several test cases. The first line of the file specifies the number of tests T, followed by the description of each test.
Each test begins with a line containing the numbers N and M. Then, M lines follow, each describing an energy transfer plan with two integers - A and B. The followers are numbered from 1 to N.
All numbers in the input are integers. N ≥ 3. The sum of N values across all tests does not exceed 100,000. The sum of M values across all tests does not exceed 200,000. 1 ≤ A, B ≤ N. A ≠ B. Within a single test, each pair (A, B) appears at most once. Both pairs (A, B) and (B, A) cannot appear simultaneously in one test.
Output
For each test, output a line containing a permutation of numbers from 1 to N - the order in which the followers should stand to achieve energy transfer associated with the magic circle. The output order should reflect the clockwise traversal of the circle. If multiple solutions exist, output any one of them. If no solution is possible, output "Epic fail" (without quotes).