UVA1116 Puzzle

这是一个双人谜题，由 Alice 和 Bob 进行。Alice 先画一个有 $n$ 个顶点的凸多边形，并用整数 $1,2,\ldots,n$ 以任意方式给顶点编号。随后，她画出若干条互不相交的对角线（多边形的顶点不算作交点，因此对角线可以在顶点处相接而不视为相交）。Alice 把整张图保密，只把多边形的边和她画出的对角线都告诉 Bob，但不说明哪些是边、哪些是对角线。每一条边或对角线都用它的两个端点来描述。Bob 的任务是：根据这些信息，猜出这些顶点在多边形边界上的排列顺序。请你帮助他解开这个谜题。 #### 例子 如果 $n=4$，并且给出 $(1,3),(4,2),(1,2),(4,1),(2,3)$ 这五条线段（它们包含四条边和一条对角线）的端点，那么多边形边界上顶点的顺序可以确定为 $1,3,2,4$（允许循环平移与反向后等价）。 请你编写一个程序：读入 Alice 告诉 Bob 的这些边与对角线的描述（只给出每条线段的两个端点，不区分边或对角线），计算多边形边界上顶点的排列顺序，并输出结果。

输入的第一行是一个正整数，表示接下来有多少组测试数据。该行后面跟着一个空行，并且相邻两组测试数据之间也有一个空行。 每组测试数据的前两行包含两个整数 $n$ 和 $m$，其中 $4 \le n \le 10000$，$0 \le m \le n-3$。其中，整数 $n$ 表示多边形的顶点数，整数 $m$ 表示画出的对角线条数。 第三行恰好包含 $2(m+n)$ 个整数，整数之间用单个空格分隔，用来描述多边形的所有边以及部分对角线。对每个 $1 \le j \le m+n$，位置 $2j-1$ 和 $2j$ 的两个整数表示一条边或一条对角线的两个端点。边与对角线的给出顺序是任意的。输入中不存在重复的线段。

对每组测试数据，输出格式如下（相邻两组输出之间要空一行）。 输出应为一行，包含一个由 $1,2,\ldots,n$ 组成的排列，数字之间以空格分隔。该序列表示这些顶点在凸多边形边界上的顺序，并且要求序列必须以顶点 $1$ 开头且序列的第二个元素必须是 $1$ 的两个相邻顶点中编号较小的那个。