Pattern Lock

Android phones often use a pattern lock instead of a password. The lock screen shows nine dots arranged in a 3 x 3 grid, numbered 1 through 9 from the top-left corner to the bottom-right corner.

1 2 3
4 5 6
7 8 9

A pattern is set by joining dots in a chosen order, drawing one continuous stroke. A valid pattern must:

• use at least 4 dots,
• form a single connected stroke (it cannot be split into pieces),
• and visit each dot at most once.

For example, the sequence 2-1-5-3-6-8-4-7-9 is a valid pattern.

There is one extra rule about passing over a dot. If the straight segment between two dots passes through a third dot, you may connect them directly only if that middle dot has already been visited. If the middle dot has not been visited yet, you cannot connect the two dots directly, because the stroke would be forced to pass through it. In the pattern 2-1-5-3-6-8-4-7-9, the step from 7 to 9 passes over 8; it is allowed because 8 was already visited earlier. Had 8 not been visited, you could not go from 7 to 9 directly.

Chulsoo has forgotten his pattern, but the smudges on his screen reveal the shape he drew, which we describe as a geometric graph. The edges of this graph are unit segments: each edge joins two dots that lie next to each other along a row, a column, or a diagonal with no other dot strictly between them. When a step passes over an already-visited middle dot, it leaves the two unit segments on either side of that middle dot (for example, going from 7 to 9 over 8 leaves the segments 7-8 and 8-9). So the graph never contains a long segment that skips over a dot; such a step always appears as its two halves.

Given such a geometric graph, recover a pattern that could have drawn exactly it. Not every graph is recoverable: a disconnected graph can never come from a single stroke, and even some connected graphs cannot be produced by any valid pattern. Some graphs can be produced by exactly one pattern, and others by several.

The input is read from standard input and contains $T$ test cases. The first line holds the integer $T$.

Each test case begins with a line containing an integer $e$ ($3 \le e \le 24$), the number of edges of the geometric graph. Each of the next $e$ lines contains two integers $s_i$ and $d_i$ ($1 \le s_i, d_i \le 9$), describing an edge between dot $s_i$ and dot $d_i$.

Write to standard output. For each test case, if some valid pattern draws exactly the given graph, print that pattern as its dot numbers separated by single spaces. Otherwise print IMPOSSIBLE.

When more than one valid pattern draws the same graph, print the lexicographically smallest one: compare two patterns position by position, and the smaller one is the pattern whose first differing position holds the smaller dot number. Every valid pattern for a given graph visits exactly the dots that appear in the graph, so all candidate patterns have the same length.