Alice and Bob

Alice and Bob play a puzzle. Alice draws a convex polygon with $n$ vertices and labels the vertices with the integers $1, 2, \dots, n$ in an arbitrary order. She then draws some diagonals so that no two of them cross (sharing an endpoint is not considered a crossing).

Alice lists, in a single mixed collection, every side of the polygon together with the diagonals she drew, each described only by its two endpoints. She does not reveal which pairs are sides and which are diagonals. From this list alone Bob must recover the cyclic order of the vertices around the border of the polygon.

Because the polygon is convex and the diagonals never cross, the border order is uniquely determined up to rotation and reflection. Write a program that, for each puzzle, reconstructs that border order.

The first line contains one integer $d$, the number of puzzles ($1 \le d \le 20$).

Each puzzle is given on two lines.

• The first line contains two integers $n$ and $m$ ($3 \le n \le 10\,000$, $0 \le m \le n - 3$): the number of vertices and the number of diagonals.
• The second line contains $2(m + n)$ integers describing the $n$ sides and the $m$ diagonals. For each $j$ with $1 \le j \le m + n$, the integers at positions $2j-1$ and $2j$ are the endpoints $a_j$ and $b_j$ of one side or diagonal, with $1 \le a_j, b_j \le n$ and $a_j \ne b_j$.

The sides and diagonals appear in an arbitrary order and there are no duplicates. Every puzzle is guaranteed to have a solution.

Print exactly $d$ lines, one per puzzle. For the $i$-th puzzle, print a permutation of $1, 2, \dots, n$: the vertices in the order they appear around the border of the polygon. The sequence must start at vertex $1$, and its second element must be the smaller of the two border neighbours of vertex $1$.