题目描述

这是一个双人谜题，参与者为Alice和Bob。Alice绘制一个包含$n$个顶点的凸多边形，并随机用整数$1, 2, \dots, n$为顶点编号。接着，她画出若干条不相交的对角线（多边形的顶点不被视为交点）。她将多边形的边和对角线的端点信息告诉Bob，但不会说明哪些是边，哪些是对角线。每条边或对角线由其两个端点表示。Bob需要根据这些信息推断出多边形顶点在边界上的顺序。请你帮助Bob解决这个谜题。

示例

如果$n = 4$，且给出的边和对角线的端点为$(1,3), (4,2), (1,2), (4,1), (2,3)$，则多边形顶点在边界上的顺序为$1, 3, 2, 4$（允许循环移位或反转）。

任务

编写一个程序，对每个输入数据集：
读取Alice提供给Bob的边和对角线描述；
计算多边形顶点在边界上的顺序；
输出结果。

输入格式

输入的第一行包含一个正整数$d$，表示数据集的数量（$1 \leq d \leq 20$）。接下来是$d$个数据集。

每个数据集由两行组成：
第一行包含两个整数$n$和$m$，分别表示多边形的顶点数和对角线数（$3 \leq n \leq 10\,000$，$0 \leq m \leq n - 3$）；
第二行包含$2(m + n)$个整数，表示所有边和部分对角线的端点。每两个整数表示一条边或对角线的两个端点（$a_j, b_j$，$1 \leq a_j \leq n$，$1 \leq b_j \leq n$，$a_j \neq b_j$）。边和对角线的顺序是任意的，且不会重复。

Alice不会作弊，即谜题始终有解。

输出格式

输出$d$行，每行对应一个数据集的解。每行包含$n$个用空格分隔的整数，即多边形边界上顶点的顺序排列（从$1$开始，第二个元素是$1$的两个边界邻居中较小的那个）。

输入数据 1

1
4 1
1 3 4 2 1 2 4 1 2 3

输出数据 1

1 3 2 4

来源

中欧 2001