Puzzle

This is a puzzle game to be played by two persons, Alice and Bob. Alice draws an n-vertex convex polygon and numbers its vertices with integers 1, 2, . . . , n in an arbitrary way. Then she draws a number of non-crossing diagonals (the vertices of the polygon are not considered to be crossing points). She keeps the drawing secret and tells Bob the polygon’s sides and diagonals, without revealing which are which. Each side or diagonal is specified by its endpoints. Bob has to guess the order of the vertices on the border of the polygon. Help him solve the puzzle. Example If n = 4 and (1,3), (4,2), (1,2), (4,1), (2,3) are the endpoints of the four sides and one diagonal then the ordering of the vertices on the border of the polygon is 1, 3, 2, 4 (up-to shifting and reversing). Write a program that reads the description of sides and diagonals given to Bob by Alice, computes the order of vertices on the border of the polygon and writes the result. Input The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The first two lines of the input contain two integers n and m, such that 4 ≤ n ≤ 10000 and 0 ≤ m ≤ n − 3. Integer n is the number of vertices of the polygon and integer m is the number of its diagonals, respectively. The third line contains exactly 2(m + n) integers separated by single spaces, specifying all sides and some diagonals of the polygon. Integers on positions 2j − 1 and 2j, 1 ≤ j ≤ m + n, specify the two endpoints of a side or a diagonal. The sides and the diagonals can be given in an arbitrary order. There are no duplicates. Output For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The output should consist of a single line containing a permutation of 1, 2, . . . , n separated by spaces. This sequence corresponds to the numbers of vertices on the border of the polygon; the sequence should always start with vertex number 1 and its second element should be the smaller vertex of the two neighbor vertices of vertex 1. Sample Input 1 4 1 1342124123 Sample Output 1324